## Algorithm

E. Bus Video System
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 yx�−�. 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 a1,a2,,an�1,�2,…,�� (exactly one number for each bus stop), where ai�� is the record for the bus stop i. The bus stops are numbered from 11 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 00 to w passengers inclusive).

Input

The first line contains two integers n and w (1n1000,1w109)(1≤�≤1000,1≤�≤109) — the number of bus stops and the capacity of the bus.

The second line contains a sequence a1,a2,,an�1,�2,…,�� (106ai106)(−106≤��≤106), where ai�� 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
Copy
3 52 1 -3
output
Copy
3
input
Copy
2 4-1 1
output
Copy
4
input
Copy
4 102 4 1 2
output
Copy
2
Note

In the first example initially in the bus could be 0011 or 22 passengers.

In the second example initially in the bus could be 112233 or 44 passengers.

In the third example initially in the bus could be 00 or 11 passenger.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 1;
int n, w, a[1001];

int main() {
cin >> n >> w;
for(int i = 0; i < n; ++i)
cin >> a[i];

long long to = 0, mn = 1e18, mx = -1e18;
for(int i = 0; i < n; ++i) {
to += a[i];
mn = min(mn, to);
mx = max(mx, to);
}

mn = min(mn, 0ll);
mx = max(mx, 0ll);

if((w - mx) + mn + 1 < 0)
cout << 0 << endl;
else
cout << (w - mx> + mn + 1 << endl;

return 0;
}
Copy The Code &

Input

cmd
3 5
2 1 -3

Output

cmd
3