Description

Irahc is an experienced explorer leading an expedition trapped in a vast icy cave system. The team has $m$ members (including Irahc). The caves form a straight line of $n$ connected chambers, each capable of sheltering a certain number of team members. Some chambers are so small that they cannot accommodate even a single person. Specifically, the $i$-th chamber can house $a_i$ members.

The entire expedition team, including Irahc, must be assigned to these chambers. As the team leader, Irahc wants to minimize the distance to the farthest member from himself, measured by the number of caves between them along the line.

As Irahc's assistant, you need to determine the smallest possible maximum distance between Irahc and any other team member.

If it is impossible to house all members in the available caves, output $\texttt{-1}$.

Format

Input

The first line contains two integers $n,m\,(1\leq n\leq 10^6, 1\leq m\leq 10^9)$, the number of chambers and the number of team members.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n\,(0\leq a_i\leq 10^6)$, where $a_i$ is the capacity of the $i$-th chamber.

Output

Only one integer: the smallest possible maximum distance between Irahc and any other team member. Or $\texttt{-1}$, if it is impossible to house all members.

Samples

2 3
1 1

-1

3 2
1 0 1

2