몰이 사냥 2

메이플스토리 무릉도장에서 수련을 하던 소공은 $N$ 마리의 몬스터가 있는 일자 지형 맵에 가만히 서서 몰이 사냥을 하고자 한다. 맵이 일자 지형으로 생겼으므로 맵 내 임의의 위치를 수 하나로 표현할 수 있다. 편의상 몬스터는 항상 정수 위치에만 있으며, 어떠한 순간에도 서로 다른 몬스터는 같은 위치에 있을 수 없다.

맵 상 $N$ 마리의 몬스터에게 $1$부터 $N$까지 서로 다른 정수 번호가 매겨져 있다. $i$ 번 ($1 \le i \le N$) 몬스터의 위치는 $d_i$다.

소공은 체인 라이트닝 스킬을 사용하여 몬스터를 사냥하려고 한다. 체인 라이트닝 스킬은 처음 지정한 몬스터에서 시작하여 양 옆으로 정확히 $1$ 차이나는 위치에 있는 몬스터에 전격이 옮겨지며, 이 과정이 더 이상 전격이 옮겨질 몬스터가 없어질 때까지 반복된다. 예를 들어, 각 몬스터의 위치가 $[1, 3, 4, 5, 6, 9, 10]$라고 하자. 소공이 위치 $4$에 있는 몬스터에게 체인 라이트닝을 사용하면, 최종적으로 위치 $3$부터 위치 $6$에 있는 몬스터까지 총 $4$ 마리의 몬스터를 공격하게 된다. 또한, 위치 $9$에 있는 몬스터에게 체인 라이트닝을 사용하면, 최종적으로 위치 $9$부터 위치 $10$에 있는 몬스터까지 총 $2$ 마리의 몬스터를 공격하게 된다.

소공은 최대한 많은 수의 몬스터를 공격하고 싶기 때문에, 비용을 들여 몬스터의 위치를 옮기려고 한다. $1$ 메소를 사용하여 몬스터의 위치를 $1$ 감소시키거나, $1$ 증가시킬 수 있다. 몬스터가 이동한 후에도 위치는 항상 정수이어야 하며, 서로 다른 몬스터는 같은 위치에 있을 수 없다.

소공은 현재 $B$ 메소를 가지고 있다. 최대 $B$ 메소를 사용하여, 한 번의 스킬 사용으로 최대한 많은 몬스터를 공격할 수 있도록 몬스터의 위치를 재배열해보자.

입력 형식

첫 줄에 몬스터의 수를 나타내는 정수 $N$과 소공의 재산을 나타내는 정수 $B$가 공백으로 구분되어 주어진다. ($1 \le N \le 1\,000\,000$; $0 \le B \le 10^{18}$)

두 번째 줄에 각 몬스터의 위치를 나타내는 $N$ 개의 정수가 공백으로 구분되어 주어진다. $i$ 번째로 주어지는 수는 $i$ 번 몬스터의 위치를 나타내는 수 $d_i$이다. ($1 \le d_i \le 1\,000\,000\,000$; $d_i < d_{i+1}$)

출력 형식

최대 $B$ 메소를 사용하여, 최대한 많은 몬스터를 공격하도록 몬스터를 재배열했을 때 한 번의 스킬 사용으로 공격할 수 있는 몬스터의 수를 출력한다.

예제 1

7 4
1 5 6 8 11 14 15

4

예제 2

7 3
1 5 6 8 11 14 15

3

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설