最近Luba拿到了一张信用卡并开始使用它。让我们考虑 Luba 连续 n 天使用该卡。
她的账户上的资金为 0。
在第 i 天的晚上,发生了一笔交易 ai。如果 ai > 0,则 ai bourles 会存入 Luba 的账户。如果 ai < 0,则撤回 ai bourles。如果ai = 0,则检查Luba账户上的金额。
在 n 天的任何一天的早上,Luba 都可以去银行将任意正整数数量的 burles 存入她的帐户。但有一个限制:账户上的金额永远不能超过d。
晚间某些交易的金额可能会大于 d。在这种情况下,答案将为“-1”。
Luba 不得超过此限制,并且她希望每天检查她的帐户(ai = 0 的日子)她帐户上的金额为非负数。去银行需要很多时间,因此 Luba 想知道她需要将一些钱存入她的帐户的最少天数(如果可以满足所有要求)。帮助她!
输入
第一行包含两个整数n、d (1 ≤ n ≤ 105, 1 ≤ d ≤ 109)——天数和金额限制。
第二行包含n个整数a1, a2, ... an ( - 104 ≤ ai ≤ 104),其中ai表示第i天的交易。
输出
如果 Luba 无法按照满足要求的方式将钱存入她的账户,则打印 -1。否则打印 Luba 必须存钱的最少天数。
示例
输入 #1
5 10 -1 5 0 -5 3
输出 #1
0
输入 #2
3 4 -10 0 20
输出 #2
-1
输入 #3
5 10 -5 0 10 -11 0
输出 #3
2