The busses in Berland are equipped with a video surveillance system. The system records information about changes in the number of passengers in a bus after stops.

If $x$ is the number of passengers in a bus just before the current bus stop and $y$ is the number of passengers in the bus just after current bus stop, the system records the number $y-x$. So the system records show how number of passengers changed.

The test run was made for single bus and $n$ bus stops. Thus, the system recorded the sequence of integers $a_1, a_2, \dots, a_n$ (exactly one number for each bus stop), where $a_i$ is the record for the bus stop $i$. The bus stops are numbered from $1$ to $n$ in chronological order.

Determine the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to $w$ (that is, at any time in the bus there should be from $0$ to $w$ passengers inclusive).


-----Input-----

The first line contains two integers $n$ and $w$ $(1 \le n \le 1\,000, 1 \le w \le 10^{9})$ — the number of bus stops and the capacity of the bus.

The second line contains a sequence $a_1, a_2, \dots, a_n$ $(-10^{6} \le a_i \le 10^{6})$, where $a_i$ equals to the number, which has been recorded by the video system after the $i$-th bus stop.


-----Output-----

Print the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to $w$. If the situation is contradictory (i.e. for any initial number of passengers there will be a contradiction), print 0.


-----Examples-----
Input
3 5
2 1 -3

Output
3

Input
2 4
-1 1

Output
4

Input
4 10
2 4 1 2

Output
2



-----Note-----

In the first example initially in the bus could be $0$, $1$ or $2$ passengers.

In the second example initially in the bus could be $1$, $2$, $3$ or $4$ passengers.

In the third example initially in the bus could be $0$ or $1$ passenger.

Difficulty: introductory

Starter code:

Solutions:
stops, cap = map(int,input().split())

a = list(map(int,input().split()))

start_max = cap
start_min = 0

current = 0
for x in a:
    current += x
    start_max = min(cap-current, start_max)
    start_min = max(start_min,-current)
    if abs(current) > cap:
        print (0)
        break
else:
    if start_max<start_min:
        print (0)
    else:
        print (start_max-start_min + 1)

data1 = list(map(int, input().split()))
data2 = list(map(int, input().split()))
k = 0
o = 0
h = 0
for i in range(data1[0]):
    k += data2[i]
    if k >= o:
        o = k
    if k < h:
        h = k
ans = data1[1] - (o + abs(h)) + 1
if ans > 0:
    print(ans)
else:
    print(0)

n, w = list(map(int, input().split()))
v = list(map(int, input().split()))

mini, maxi = 0, 0
s = 0
for i in range(n):
    s += v[i]
    mini = min(mini, s)
    maxi = max(maxi, s)

res = max(0, w - (maxi - mini) + 1)
print(res)


N, W = (int(i) for i in input().split())
L = [int(i) for i in input().split()]

n = 0
left = 0
right = W

for i in L:
    n += i
    if n + right > W:
        right -= n + right - W
    if n + left < 0:
        left += -(n + left)

print(max(right - left + 1, 0))


n,m=map(int,input().split())
a=list(map(int,input().split()))
mi=0
ma=0
k=0
for i in range(n):
    k+=a[i]
    if k>ma:
        ma=k
    if k<mi:
        mi=k
if m-ma+mi+1<0:
    print(0)
else:
    print(m-ma+mi+1)

n, w = map(int, input().split())
a = list(map(int, input().split()))
mx, mn, bal = 0, 0, 0
for aa in a:
	bal += aa
	mx, mn = max(mx, bal), min(mn, bal)
left, right = - mn, w - mx
if right < 0 or left > right:
	print(0)
else:
	print(right - left + 1)

n, w = list(map(int, input().split()))
a = list(map(int, input().split()))

s = 0
min_s = 10000000
max_s = -10000000

for i, e in enumerate(a):
	s += e

	min_s = min(s, min_s)
	max_s = max(s, max_s)

if -min_s > w:
	print(0)
	quit()

if max_s > w:
	print(0)
	quit()

if max_s >= 0 and min_s >= 0:
	max_s = w - max_s + 1
elif max_s >=  0 and min_s < 0:
	max_s = w - max_s + min_s + 1
elif max_s < 0:
	max_s = w + min_s + 1



if max_s < 0:
	print(0)
else:
	print(max_s)

T = input().split(' ')
n = int(T[0])
w = int(T[1])
S = input().split(' ')
for i in range(len(S)):
    S[i] = int(S[i])
m = 0
M = 0
t = 0
for i in range(len(S)):
    t+=S[i]
    M = max(M, t)
    m = min(m, t)
if -m <= w - M:
    print(w - M + m + 1)
else:
    print(0)


stops,m = list(map(int,input().split()))
people = [int(i) for i in input().split()]

cM = 0
cm = 0
c = 0
for i in range(stops):
    c += people[i]
    if c > cM:
        cM = c
    if c <cm:
        cm = c

print(m-cM+cm+1 if m-cM+cm+1>=1 else 0)


n, w = map(int, input().split())
maxp, minp = 0, 0
a = list(map(int, input().split()))
now = 0
for i in range(n):
    now += a[i]
    maxp = max(maxp, now)
    minp = min(minp, now)
print(max(0, w - maxp + minp + 1))

n, m = map(int, input().split())
f, s = 0, 0
p = 0
for i in list(map(int, input().split())):
    p += i
    if p < 0:
        f = min(f, p)
    if p > 0:
        s = max(s, p)
print(0 if s > m or -f > m or m - s < -f else m - s + f + 1)

n, w = list(map(int, input().split()))
ar = list(map(int, input().split()))

difs = []
s = 0
for x in range(n):
    s += ar[x]
    difs.append(s)

minn, maxx = min(difs), max(difs)
maxres, minres = w, 0
if maxx > 0:
    maxres -= maxx
if minn < 0:
    minres -= minn

if maxres < 0 or minres > w or minres > maxres:
    print(0)
else:
    print(maxres - minres + 1)


n, w = list(map(int, input().split()))
cur_delta = max_delta = min_delta = 0
for ai in map(int, input().split()):
	cur_delta += ai
	max_delta = max(max_delta, cur_delta)
	min_delta = min(min_delta, cur_delta)
min_res = 0-min_delta
max_res = w-max_delta
if max_res < min_res:
	print('0')
else:
	print(max_res+1-min_res)


n, w = map(int, input().split())
a = [int(i) for i in input().split()]
res = [0] * (n + 1)
for i in range(n):
    res[i] = a[i]
    res[i] += res[i - 1]
r = w
l = 0
for i in range(n):
    r = min(r, w - res[i])
    l = max(l, -res[i])
print(max(r - l + 1, 0))

n, w = list(map(int, input().split()))
arr = list(map(int, input().split()))
mx = 0
mn = 0
curr = 0
for i in arr:
    curr += i
    mx = max(curr, mx)
    mn = min(curr, mn)
ans = w + 1 - (mx - mn)
if ans < 0:
    print(0)
else:
    print(ans)

import sys

_, max_capacity = list(map(int, next(sys.stdin).rstrip().split()))

xs = list(map(int, next(sys.stdin).rstrip().split()))

current = 0
max_x = 0
min_x = 0

for x in xs:
    current += x
    max_x = max(max_x, current)
    min_x = min(min_x, current)

calibration = max_x - min_x

if calibration > max_capacity:
    print(0)
else:
    print(max_capacity - calibration + 1)


n, w = list(map(int, input().split()))
a = list(map(int, input().split()))

max_p = 0
min_p = 0

s = 0
for step in a:
    s += step
    if s > max_p:
        max_p = s
    if s < min_p:
        min_p = s

d = max_p - min_p

#print(max_p, min_p, d)

if w - d + 1 > 0:
    print(w - d + 1)
else:
    print(0)


(n, l) = list(map(int, input().split()))
maxim = 0
min = 0
x = 0
a = list(map(int, input().split()))
for i in range(n):
    x += a[i]
    if x > maxim:
        maxim = x
    if x < min:
        min = x
if (maxim-min) > l:
    print(0)
else:
    print(l-(maxim-min)+1)



from itertools import accumulate

def main():
	n, w = [int(_) for _ in input().split()]
	a = [int(_) for _ in input().split()]

	c = list(accumulate(a))

	# print(a)
	# print(c)
	# print(max(c), min(c))

	ans = min(w, w - max(c)) - max(-min(c), 0) + 1
	if ans <= 0:
		print(0)
	else:
		print(ans)
def __starting_point():
	main()

__starting_point()

n, w = list(map(int, input().split()))
a = list(map(int, input().split()))
prefix = [0]
summ = 0
for i in range(n):
	summ += a[i]
	prefix.append(summ)
r = max(prefix)
t = min(prefix)
cnt1 = 0
if t < 0:
	cnt1 += abs(t)
cnt2 = w - r
if cnt2 - cnt1 + 1 <= 0:
	print(0)
else:	
	print(cnt2 - cnt1 + 1)	



# Project name: CF-481-E-D3

n,w = map(int, input().split())
a = list(map(int, input().split()))
r=[0]
for i in a:
    r+=[r[-1]+i]

if (((w-max(r)+1)+min(r))) <0:
    print (0)
else: print ((w-max(r)+1)+min(r))

n, w = list(map(int, input().split()))
L = list(map(int, input().split()))
maxim = 0
minin = 0
summa = 0
for i in range(n):
    summa += L[i]
    if summa > maxim:
        maxim = summa
    if summa < minin:
        minin = summa
print(max(0, w - maxim + minin + 1))


n, w = list(map(int, input().split()))
a = list(map(int, input().split()))
cur = 0
mn, mx = 0, w
for el in a:
    cur += el
    if cur < 0:
        mn = max(mn, abs(cur))
    else:
        mx = min(mx, w - cur)
if mn > mx:
    print(0)
else:
    print(mx - mn + 1)


from itertools import accumulate

n, w = list(map(int, input().split()))
a = list(map(int, input().split()))

s_a = [0] + list(accumulate(a))
mn, mx = min(s_a), max(s_a)

mn_ = max(0, -mn)
mx_ = w - mx

if mx_ < 0 or mx_ < mn_ or mn_ > w or mx - mn > w or mx_ - mn_ > w or mn < -w or mx > w or min(a) < -w or max(a) > w:
    print(0)
    return

print(mx_ - mn_ + 1)


n, w = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
mx = 0
mn = 0
cur = 0
for aa in a:
    cur += aa
    mx = max(cur, mx)
    mn = min(cur, mn)

up = w - mx + 1
down = abs(mn)
if down > up:
    print(0)
else:
    print(up - down)