After Rock was arrested for "Reckless Driving", he had returned to Punny Bunny Prison.
Punny Bunny Prison has $N$ prison cells numbered from $1$ to $N$, and each cell has a prisoner.
Rock is the prisoner in cell $1$.

Rock believes the key to his Great Escape lies in cell $N$, where he has the highest chance of escaping.
Therefore, with his $M$ chocolate coins, he would like to bribe certain prisoners to swap cells with himself.
Let $[c_1, c_2, c_3, \dots, c_N]$ be the cost to bribe the $i$th prisoner, note that $c_1=0$.
To avoid suspicion, Rock chooses a number $K$ $(1\le K\le N-1)$ on day $0$.
From day $1$ onwards, if Rock is in cell $i$, he may pick prisoner $j$ ($i+1\le j\le min(N, i+K)$) if he has more than or the same number of chocolate coins than the bribe cost of prisoner $j$. Formally, $M \ge c_j$. He loses $c_j$ chocolate coins after the bribe.
He repeats the above operations until he reaches cell $N$ or is unable to bribe any more prisoners.

Rock would like to minimize $K$ while being able to reach cell $N$.
Please help Rock escape Punny Bunny Prison by finding the smallest $K$ or report that no such $K$ exists.

Input

The first line of input contains two integers, $N$ and $M$, denoting the number of prison cells and his initial number of chocolate coins.
The second line of input contains $N$ integers, $[c_1, c_2, c_3, \dots, c_N]$, denoting the bribe cost of the $i$th prisoner.

Output

Output an integer: the minimum $K$ possible. If no such $K$ exists, output $-1$ instead.

Constraints

For all subtasks, $2\le N\le 2\times 10^6$, $1\le M,c_i\le 10^9$
Subtask 1 (20%): $2\le N\le 16$
Subtask 2 (20%): $2\le N\le 300$
Subtask 3 (30%): $2\le N\le 2000$
Subtask 4 (30%): No additional constraints