Yuki is a magical girl who has $n$ pieces of ice, where the mass of the $i$-th piece is $a_i$.

For every positive integer $t$:

• At time $(t-0.5)$, Yuki can use her magic on at most $k$ distinct not-fully-melted (i.e., mass greater than $0$) pieces of ice, increasing their mass by $1$.
• At time $t$, every piece of ice melts, and their mass decreases by $1$.

Yuki needs you to find the maximum non-negative integer $s$ such that at time $s$ and all times before $s$, Yuki can use her magic to ensure that no piece of ice has completely melted (i.e., the mass of every piece of ice remains greater than $0$).

Input

The first line contains two positive integers $n, k$.

The second line contains $n$ positive integers $a_1, \dots, a_n$.

Output

Output a single line containing a non-negative integer, representing the maximum non-negative integer $s$ such that at time $s$ and all times before $s$, Yuki can use her magic to ensure that no piece of ice has completely melted.

Examples

Input 1

3 1
3 1 4

Output 1

2

Note

Yuki can use her magic as follows:

• At time $0.5$, Yuki uses her magic on the $2$nd piece of ice. The masses of the $3$ pieces are $3, 2, 4$.
• At time $1$, all ice melts. The masses of the $3$ pieces are $2, 1, 3$.
• At time $1.5$, Yuki uses her magic on the $2$nd piece of ice. The masses of the $3$ pieces are $2, 2, 3$.
• At time $2$, all ice melts. The masses of the $3$ pieces are $1, 1, 2$.

It is easy to prove that at time $3$, at least one piece of ice must have completely melted, so the maximum integer $s$ satisfying the requirements is $2$.

Input 2

ice/ice2.in

Output 2

ice/ice2.ans

Note

This test case satisfies the constraints of test point $3$.

Input 3

ice/ice3.in

Output 3

ice/ice3.ans

Note

This test case satisfies the constraints of test point $5$.

Input 4

ice/ice4.in

Output 4

ice/ice4.ans

Note

This test case satisfies the constraints of test point $6$.

Input 5

ice/ice5.in

Output 5

ice/ice5.ans

Note

This test case satisfies the constraints of test point $9$.

Input 6

ice/ice6.in

Output 6

ice/ice6.ans

Note

This test case satisfies the constraints of test point $10$.

Constraints

For all test data:

• $2 \le n \le 10^6$
• $1 \le k \le n-1$
• $1 \le a_i \le 10^6$

Special Property: All pieces of ice have equal mass, i.e., $a_1 = a_2 = \dots = a_n$.