Recently, Country H has been building a signal transmission channel. This channel will pass through $n + 2$ cities in sequence, which are distributed exactly along the $x$-axis. Let us label them as city $0$ to city $n + 1$, such that the coordinate of city $i$ is exactly $i$.

Among these $n + 2$ cities, only city $0$ and city $n + 1$ already have signal base stations built. You may also build signal base stations in some (or zero) of the cities from $1$ to $n$ to improve the quality of this signal transmission channel and gain a certain amount of public satisfaction.

Specifically, if you choose to build a signal base station in city $i$, you gain $a_i$ in public satisfaction. The quality index of the signal transmission channel is defined as the minimum distance between any two adjacent base stations in the channel.

Country H has found the top engineer in the country, which is you, to design the construction method for this signal transmission channel. Under the condition that the total public satisfaction gained is at least $W$, maximize the quality index of this signal transmission channel.

Input

The first line contains two integers $n$ and $W$ ($0 \le n \le 2 \times 10^5$, $0 \le W \le 10^{18}$).

The second line contains $n$ integers, where the $i$-th integer represents $a_i$ ($0 \le a_i \le 10^9$).

Output

Output a single integer representing the maximum quality index of the constructed signal transmission channel. If there is no solution, output -1.

Examples

Input 1

11 12
1 2 1 2 6 2 1 2 1 2 1

Output 1

2