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, ..., 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 ≤ n ≤ 1 000, 1 ≤ w ≤ 10^{9}) — the number of bus stops and the capacity of the bus.

The second line contains a sequence a_1, a_2, ..., a_n (-10^{6} ≤ a_i ≤ 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.
//package Codeforces.Div3.Round_481.E_Bus_Video_System;

import java.io.*;
import java.util.*;

public class E_Bus_Video_System {

    public static PrintWriter out;
    public static void main(String[] args) throws IOException {

        boolean fileInOut = E_Bus_Video_System.class.getPackage() != null;

        Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(fileInOut ? E_Bus_Video_System.class.getResourceAsStream("in.txt") : System.in)));
        out = new PrintWriter(new BufferedOutputStream(fileInOut ? new FileOutputStream("out.txt") : System.out), true);

        int testCase = fileInOut ? sc.nextInt() : 1;

        for (int i = 0; i < testCase; i++) {

            int n = sc.nextInt();
            int w = sc.nextInt();

            int[] b = new int[n];

            for (int bIndex = 0; bIndex < b.length; bIndex++) {
                b[bIndex] = sc.nextInt();
            }

            new E_Bus_Video_System().solution(n, w, b);
        }

        if (fileInOut) {
            verify(E_Bus_Video_System.class.getResource("ans.txt").getFile());
        }
    }
    public static void verify(String ansFile) throws IOException {

        String outputFile = "out.txt";

        BufferedReader reader1 = new BufferedReader(new FileReader(ansFile));
        BufferedReader reader2 = new BufferedReader(new FileReader(outputFile));

        String line1 = reader1.readLine();
        String line2 = reader2.readLine();

        boolean areEqual = true;
        int lineNum = 1;

        while (line1 != null || line2 != null) {

            if (line1 == null || line2 == null) {

                areEqual = false;
                break;
            } else if (!line1.equals(line2)) {

                areEqual = false;
                break;
            }

            line1 = reader1.readLine();
            line2 = reader2.readLine();

            lineNum++;
        }

        if (areEqual) {

            System.out.println("All Test Cases Passed !");
        } else {

            System.out.println("Output differ at line " + lineNum);
            System.out.println("ans.txt has " + line1 + " and out.txt has " + line2 + " at line " + lineNum);
        }

        reader1.close();
        reader2.close();
    }

    public void solution(int n, int w, int[] B) {

        int minB = Integer.MAX_VALUE;
        int maxB = Integer.MIN_VALUE;

        int currentPassengerCount = 0;
        for (int i = 0; i < B.length; i++) {
            currentPassengerCount += B[i];
            minB = Math.min(minB, currentPassengerCount);
            maxB = Math.max(maxB, currentPassengerCount);
        }

        if (maxB > w) {
            out.println(0);
            return;
        }

        int l = 0;
        int r = w;

        if (minB < 0) {
            l = -minB;
        }

        if (maxB > 0) {
            r = w - maxB;
        }

        if (l > r) {
            out.println(0);
            return;
        }

        out.println(r - l + 1);
    }
}
