CF893D.Credit Card

Recenlty Luba got a credit card and started to use it. Let's consider n consecutive days Luba uses the card.

She starts with 0 money on her account.

In the evening of i-th day a transaction a__i occurs. If a__i > 0, then a__i bourles are deposited to Luba's account. If a__i < 0, then a__i bourles are withdrawn. And if a__i = 0, then the amount of money on Luba's account is checked.

In the morning of any of n days Luba can go to the bank and deposit any positive integer amount of burles to her account. But there is a limitation: the amount of money on the account can never exceed d.

It can happen that the amount of money goes greater than d by some transaction in the evening. In this case answer will be «-1».

Luba must not exceed this limit, and also she wants that every day her account is checked (the days when a__i = 0) the amount of money on her account is non-negative. It takes a lot of time to go to the bank, so Luba wants to know the minimum number of days she needs to deposit some money to her account (if it is possible to meet all the requirements). Help her!

最近，Luba 办了一张信用卡并开始使用它。我们考虑 Luba 连续使用该卡的 n 天。

她账户的初始余额为 0。

在第 i 天晚上会发生一笔交易 a__i。若 a__i > 0，则向 Luba 的账户存入 a__i 博尔（bourles）；若 a__i < 0，则从账户中取出 |a__i| 博尔；若 a__i = 0，则检查账户余额。

在任意一天的早晨（共 n 天），Luba 都可以前往银行，向其账户存入任意正整数金额的博尔。但有一个限制：账户余额任何时候都不能超过 d。

有可能某天晚上的交易导致余额超过 d。此时答案为 «-1»。

Luba 必须遵守这一上限限制；此外，她还要求：每次账户被检查的那天（即满足 a__i = 0 的那些天），账户余额必须为非负数。由于去银行耗时较多，Luba 想知道：在满足所有条件的前提下，她最少需要多少天前往银行存款（如果满足所有条件是不可能的，则输出相应结果）。请帮帮她！

The first line contains two integers n, d (1 ≤ n ≤ 105, 1 ≤ d ≤ 109) —the number of days and the money limitation.

The second line contains n integer numbers _a_1, _a_2, ... a__n ( - 104 ≤ a__i ≤ 104), where a__i represents the transaction in i-th day.

第一行包含两个整数 $n$、$d$（$1 ≤ n ≤ 10^5$，$1 ≤ d ≤ 10^9$）——分别表示天数和资金限额。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$-10^4 ≤ a_i ≤ 10^4$），其中 $a_i$ 表示第 $i$ 天的交易额。

Print -1 if Luba cannot deposit the money to her account in such a way that the requirements are met. Otherwise print the minimum number of days Luba has to deposit money.

如果露芭无法以满足要求的方式向她的账户存款，则输出 $-1$；否则输出露芭所需存款的最少天数。