Willoughby the witch is concocting a nefarious stew in her basement cauldron, which can be modelled as an array with \(N\) indexes. She places \(N\) ingredients in a circle at the same time and lets her magical cauldron swirl them around counterclockwise at a constant speed. Each of her ingredients, however, can have different speeds and thus move at a speed of \(A_{i}\) indexes around the cauldron per second. Willoughby notices that as her ingredients swirl around, some of them end up at the same index for a brief moment in time. Intrigued, she wonders to herself the following:

What is the maximum amount of ingredients that can be on the same index after \(T\) seconds, if she can magically increment or decrement the speed of any one of her ingredients by one index per second?

Constraints

\(1 \le A_{i} \le 2N\)

Subtask 1 [30%]

\(1 \le N,T \le 10 ^ 3\)

Subtask 2 [70%]

\(1 \le N \le 10 ^ 5\)

\(1 \le T \le 10 ^ 7\)

Input Specification

The first line of input consists of integers \(N\) and \(T\), representing the number of ingredients and the time elapsed respectively.

The next line consists of \(N\) space-separated integers \(A_{i}\), representing the speed at which the \(i\)th ingredient travels counterclockwise (to the left and wrapping around from the right).

Output Specification

Output the maximum amount of ingredients on same index after \(T\) seconds.

Sample Input

5 2
3 4 2 1 2

Sample Output

3

Explanation for Sample Output

We can label each ingredient by their starting index, assuming a one-indexed array.

At \(T=0\), each ingredient is at their initial positions, so the array looks like \([1,2,3,4,5]\).

At \(T=1\), there is one ingredient at index 1 and four ingredients at index 3. The array looks like \([[3],[],[1,2,4,5],[],[]]\).

At \(T=2\), there is one ingredient for each index of 0, 1, and 4, and two ingredients at index 3. The array looks like \([[5],[4],[],[2,3],[1]]\).

Currently, we have one or two ingredients at the same index after \(2\) seconds. We can change the intial speed of the fifth ingredient from \(2\) to \(3\) in order to have three ingredients at index 4 after \(2\) seconds. The array at \(T=2\) would look like \([[],[4],[],[2,3,5],[1]]\).

It can be seen that there will be at most three ingredients on the same index after changing the speed of any ingredient by at most 1. Thus, we output 3.