#P0845. 攒钱买礼物

攒钱买礼物

题目描述

训练营附近新开了一家小店,橱窗里摆着一个小明很想买的礼物,价格是 x 元。

小明决定每天训练结束后,把当天攒下的钱放进自己的小罐子里。第 i 天他可以存入 aia_i 元。

请问最早在第几天结束后,小明罐子里的钱不少于 x 元,可以买下这个礼物?

如果直到第 n 天结束后仍然不够,输出 -1。

输入格式

第一行输入两个整数 n 和 x,表示天数和礼物价格。

第二行输入 n 个整数 a_i,表示每天存入的钱数。

输出格式

输出一行,一个整数,表示最早攒够钱的天数;如果攒不够,输出 -1。

样例 1

5 9
3 2 4 1 5
3

样例 2

5 20
3 2 4 1 5
-1

样例说明

样例 1 中,每天结束后的总存款依次为 3, 5, 9, 10, 15,第 3 天第一次达到 9 元。

数据范围

  • 1≤n≤1000001 \le n \le 100000
  • 0≤x≤10180 \le x \le 10^{18}
  • 0≤ai≤1090 \le a_i \le 10^9