← 返回题目列表

Codeforces · 893/D

D. 信用卡

中文机器翻译题面 查看原题

最近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