该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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