It's already 22:30 now, and it's time for Alice to go to bed. To ensure her sleeping quality, Alice decides to turn all the lights in her bedroom off.

There are ~n~ lights, numbered from ~1~ to ~n~, arranged in a row in Alice's bedroom. Each time Alice can select an integer i and turn all the lights numbered from ~i~ to ~(i + X - 1)~ (both inclusive) off, where ~X~ is a predefined positive integer. Note that each time the value of ~X~ must be the same.

Given the initial status of all the lights, please help Alice determine the smallest possible ~X~ so that she can turn all the lights off within ~k~ times.

Input

• The first line contains two integers ~n~ and ~k~ ~(1 \leq k \leq n \leq 10^6)~.
• The second line contains an array ~a~ representing the initial status of the lights. If ~a_i = 1~, the ~i-th~ light is initially on; if ~a_i = 0~, the ~i-th~ light is initially off. It is guaranteed that there is at least one ~a_i = 1~ in the array.

Output

• Output a line containing one integer, indicating the smallest possible ~X~.

Sample

Sample Input 1

3 1
0 1 0

Sample Output 1

1

Sample Input 2

7 4
0 1 0 1 1 1 1

Sample Output 2

2

Notes

In the second test,

For ~X = 1~, The operation can be perfomed by choosing following intervals

• ~[2, 2], [4, 4], [5, 5], [6, 6], [7, 7].~
• Total operations: ~4~.

For ~X = 2~, The operation can be perfomed by choosing following intervals

• ~[2, 3], [4, 5], [6, 7]~
• Total operations: ~3~.

Therefore, answer is ~2~.