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*<sub class="lower-index">*i*</sub> occurs. If *a*<sub class="lower-index">*i*</sub> &gt; 0, then *a*<sub class="lower-index">*i*</sub> bourles are deposited to Luba's account. If *a*<sub class="lower-index">*i*</sub> &lt; 0, then *a*<sub class="lower-index">*i*</sub> bourles are withdrawn. And if *a*<sub class="lower-index">*i*</sub> = 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*<sub class="lower-index">*i*</sub> = 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!
The first line contains two integers *n*, *d* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>, 1 ≤ *d* ≤ 10<sup class="upper-index">9</sup>) —the number of days and the money limitation.

The second line contains *n* integer numbers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ... *a*<sub class="lower-index">*n*</sub> ( - 10<sup class="upper-index">4</sup> ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">4</sup>), where *a*<sub class="lower-index">*i*</sub> represents the transaction in *i*-th day.
none
5 10
-1 5 0 -5 3
0
3 4
-10 0 20
-1
5 10
-5 0 10 -11 0
2
5 13756
-2 -9 -10 0 10
1
20 23036
-1 1 -1 -1 -1 -1 1 -1 -1 0 0 1 1 0 0 1 0 0 -1 -1
1
12 82016
1 -2 -1 -1 -2 -1 0 -2 -1 1 -2 2
1
7 8555
-2 -3 -2 3 0 -2 0
1
16 76798
-1 11 -7 -4 0 -11 -12 3 0 -7 6 -4 8 6 5 -10
1
20 23079
0 1 1 -1 1 0 -1 -1 0 0 1 -1 1 1 1 0 0 1 0 1
0
19 49926
-2 0 2 0 0 -2 2 -1 -1 0 0 0 1 0 1 1 -2 2 2
1
19 78701
1 0 -1 0 -1 -1 0 1 0 -1 1 1 -1 1 0 0 -1 0 0
1
10 7
-9 3 -4 -22 4 -17 0 -14 3 -2
1
9 13
6 14 19 5 -5 6 -10 20 8
-1
8 11
12 -12 -9 3 -22 -21 1 3
-1
8 26
-4 9 -14 -11 0 7 23 -15
-1
5 10
-8 -24 0 -22 12
1
10 23
9 7 14 16 -13 -22 24 -3 -12 14
-1
8 9
6 -1 5 -5 -8 -7 -8 -7
-1
3 14
12 12 -8
-1
9 9
-3 2 0 -2 -7 -1 0 5 3
2
4 100
-100 0 -50 100
1
9 5
-2 0 3 -4 0 4 -3 -2 0
1
7 4
-6 0 2 -3 0 4 0
1
6 2
-2 3 0 -2 0 0
1
1 1
2
-1
5 4
-1 0 -3 0 3
1
7 3
1 -3 0 3 -1 0 2
-1
4 4
2 2 0 1
-1
6 1
-3 0 0 0 -2 3
1
1 1
1
0
2 3
2 0
0
5 4
-1 0 0 1 -1
1
6 4
-1 0 2 -4 0 5
-1
import os
import sys
from io import BytesIO, IOBase
import math
from math import isclose

BUFSIZE = 4096
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def I():
    return input()

def II():
    return int(input())

def LII():
    return list(map(int, input().split()))

n, p = LII()
a = LII()

prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
    prefix_sum[i] = prefix_sum[i - 1] + a[i - 1]

d, b = [0] * (4 * n  + 1), [0] * (4 * n  + 1)

def build(s, t, p):
    # 对 [s,t] 区间建立线段树,当前根的编号为 p
    if s == t:
        d[p] = prefix_sum[s]
        return
    m = s + ((t - s) >> 1)
    # 移位运算符的优先级小于加减法，所以加上括号
    # 如果写成 (s + t) >> 1 可能会超出 int 范围
    build(s, m, p * 2); build(m + 1, t, p * 2 + 1)
    # 递归对左右区间建树
    d[p] = d[p * 2] + d[(p * 2) + 1]


def getsum(l, r, s, t, p):
    # [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p为当前节点的编号
    if l <= s and t <= r:
        return d[p]
    # 当前区间为询问区间的子集时直接返回当前区间的和
    m = s + ((t - s) >> 1)
    if b[p]:
        # 如果当前节点的懒标记非空, 则更新当前节点两个子节点的值和懒标记值
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # 将标记下传给子节点
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # 清空当前节点的标记
        b[p] = 0
    sum = 0
    if l <= m:
        sum = getsum(l, r, s, m, p * 2)
    if r > m:
        sum = max(sum, getsum(l, r, m + 1, t, p * 2 + 1))
    return sum

def update(l, r, c, s, t, p):
    # [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p
    # 为当前节点的编号
    if l <= s and t <= r:
        d[p] = d[p] + (t - s + 1) * c
        b[p] = b[p] + c
        return
    # 当前区间为修改区间的子集时直接修改当前节点的值, 然后打标记, 结束修改
    m = s + ((t - s) >> 1)
    if b[p] and s != t:
        # 如果当前节点的懒标记非空, 则更新当前节点两个子节点的值和懒标记值
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # 将标记下传给子节点
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # 清空当前节点的标记
        b[p] = 0
    if l <= m:
        update(l, r, c, s, m, p * 2)
    if r > m:
        update(l, r, c, m + 1, t, p * 2 + 1)
    d[p] = d[p * 2] + d[p * 2 + 1]

build(1, n, 1)

ans = 0
for i in range(1, n + 1):
    if prefix_sum[i] > p:
        print(-1)
        sys.exit()
    if a[i - 1] == 0:
        if prefix_sum[i] < 0:
            ans += 1
            val = getsum(i + 1, n, 1, n, 1)
            update(i, n, p - val, 1, n, 1)
print(ans)