3633. 双人旋转赛车

单点时限: 2.0 sec

内存限制: 1024 MB

oxx 和 Xiejiadong 在玩一个双人旋转赛车的小游戏。

他们将进行一些比赛。每局比赛必须按顺序进行,胜者会得到该局对应的分数 $x_{i}$。

由于 oxx 技艺不精(每局都可以由 Xiejiadong 决定胜负),因此他给自己设置了初始分数 $k$,希望自己能够一直领先 Xiejiadong。

不过 Xiejiadong 识破了 oxx 的诡计,现在 Xiejiadong 想知道自己至少需要赢几局才可以使得自己能够在某一时刻的比分不落后于 oxx。

若无法达到则输出 $-1$。

输入格式

第一行两个整数 $n, k$ $(1 \leq n \leq 10^6, 1 \leq k \leq 10^9)$,表示游戏局数以及 oxx 初始分数。

第二行 $n$ 个整数 $x_{i}$ $(1 \leq x_{i} \leq 10^9)$,表示每局游戏的分数。

输出格式

一个整数,表示答案。

样例

Input
3 3
4 1 2
Output
1
Input
3 7
1 2 3
Output
-1

提示

样例一:Xiejiadong 只需要赢第一局,即可获得 4 分,这时候就不落后于 oxx 3 分。

样例二:Xiejiadong 全胜也领先不了。

101 人解决,188 人已尝试。

153 份提交通过,共有 1128 份提交。

4.7 EMB 奖励。

创建: 2 年前.

修改: 2 年前.

最后提交: 1 周,2 天前.

来源: EOJ Monthly 2018.9