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.
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class l {
    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMMMM      MMMMMM      OOO      OOO        SSSS   SSS     EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEE           MMMM MMM  MMM MMMM    OOO          OOO    SSSS       SSS   EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM  MMMMMM  MMMM   OOO            OOO   SSSS             EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM  OOO              OOO   SSSSSSS         EEEEE          /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO      SSSSSS       EEEEEEEEEEE    /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO         SSSSSSS   EEEEEEEEEEE    /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM   OOO            OOO              SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM    OOO          OOO     SSS       SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM      OOO      OOO        SSS    SSSS    EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    static int mod = (int) (1e9 + 7);
    // static int n;
    static StringBuilder sol;

    static class pair implements Comparable<pair> {
        int out, in;

        public pair(int x, int y) {
            out = x;
            in = y;

        }

        public int compareTo(pair o) {
            return o.in - in == 0 ? out - o.out : o.in - in;
        }

        public String toString() {
            return out + " " + in;
        }
    }
    static int[][]memo;
    static int n;
    static int dp(int idx,int msk){
        if (msk==0)return 0;
        if (memo[idx][msk]!=-1)return memo[idx][msk];
        int ans =Integer.MAX_VALUE;
        for (int i =0;i<n;i++){
            if ((msk&1<<i)!=0){
                int x =~(1<<i);
                ans=Math.min(ans,allpairs[idx][i]+dp(i,(msk&x)));
            }
        }
        return memo[idx][msk]=ans;
    }
    static ArrayList<Integer>arr;
    static void trace(int idx,int msk){
        if (msk==0)return ;
        int ans =dp(idx,msk);
        for (int i =0;i<n;i++){
            if ((msk&1<<i)!=0){
                int x =~(1<<i);
                if (allpairs[idx][i]+dp(i,(msk&x))==ans){
                    arr.add(i+1);trace(i,(msk&x));
                    return;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        //FileWriter f = new FileWriter("C:\\Users\\Ibrahim\\out.txt");
        PrintWriter pw = new PrintWriter(System.out);
        int n =sc.nextInt();
        int w = sc.nextInt();
        int[]a= new int[n];
        for (int i =0;i<n;i++)a[i]=sc.nextInt();
        int lo=0;
        int hi=w;
        int lower=-1;
        boolean ok=true;
        while (lo<=hi){
            int mid=lo+hi>>1;
            int cur=mid;
            boolean isgrt =true;
            boolean issmal=true;
            for (int i =0;i<n;i++){
                cur+=a[i];
                if (cur<0||cur>w){
                    if (cur<0)issmal=false;
                    if (cur>w)isgrt=false;
                    break;
                }
            }
            if (isgrt&&issmal){
                lower=mid;
                hi=mid-1;
            }
            else if (!issmal){
                lo=mid+1;
            }
            else hi=mid-1;
        }
       // pw.println(lower);
        int hig=-1;
        lo=0;
        hi=w;
        while (lo<=hi){
            int mid=lo+hi>>1;
            int cur=mid;
            boolean ismal =true;
            boolean isgrt=true;
            for (int i =0;i<n;i++){
                cur+=a[i];
                if (cur<0||cur>w){
                    if (cur<0)ismal=false;
                    else isgrt=false;
                }
            }
            if (ismal&&isgrt){
                hig=mid;
                lo=mid+1;
            }
            else if (!ismal){
                lo=mid+1;
            }else hi=mid-1;
        }
        //pw.println(hig);
        if (lower==-1)ok=false;
        if (ok){
            pw.println((hig-lower)+1);
        }
        else pw.println(0);

        pw.flush();
    }
    static int[][]allpairs;
    static long gcd(long a, long b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }

    static int inver(long x, int mod) {
        int a = (int) x;
        int e = (mod - 2);
        int res = 1;
        while (e > 0) {
            if ((e & 1) == 1) {
                //System.out.println(res*a);
                res = (int) ((1l * res * a) % mod);
            }
            a = (int) ((1l * a * a) % mod);
            e >>= 1;
        }
        //out.println(res+" "+x);
        return res % mod;
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
    static final int INF = (int)1e9;	//don't increase, avoid overflow
    static ArrayList<Edge>[] adjList;
    static int V;
    static int dijkstra(int S, int T)	//O(E log E)
    {
        int[] dist = new int[V];
        Arrays.fill(dist, INF);
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
        dist[S] = 0;
        pq.add(new Edge(S, 0));						//may add more in case of MSSP (Mult-Source)
        while(!pq.isEmpty())
        {
            Edge cur = pq.remove();
            if(cur.node == T)						//remove if all computations are needed
                return dist[T];
            if(cur.cost > dist[cur.node])			//lazy deletion
                continue;
            for(Edge nxt: adjList[cur.node])
                if(cur.cost + nxt.cost < dist[nxt.node])
                    pq.add(new Edge(nxt.node, dist[nxt.node] = cur.cost + nxt.cost ));
        }
        allpairs[S]=dist;
        return -1;
    }
    static ArrayList<Integer> dijkstra2(int S, int T)	//O(E log E)
    {
        int[] dist = new int[V];
        Arrays.fill(dist, INF);
        PriorityQueue<Edge2> pq = new PriorityQueue<Edge2>();
        dist[S] = 0;
        pq.add(new Edge2(S, 0,new ArrayList<>()));						//may add more in case of MSSP (Mult-Source)
        while(!pq.isEmpty())
        {
            Edge2 cur = pq.remove();
            if(cur.node == T)						//remove if all computations are needed
                return cur.way;
            if(cur.cost > dist[cur.node])			//lazy deletion
                continue;
            for(Edge nxt: adjList[cur.node])
                if(cur.cost + nxt.cost < dist[nxt.node])
                    pq.add(new Edge2(nxt.node, dist[nxt.node] = cur.cost + nxt.cost ,cur.way));
        }
        allpairs[S]=dist;
        return null;
    }
    static class Edge implements Comparable<Edge>
    {
        int node, cost;

        Edge(int a, int b) { node = a;	cost = b; }

        public int compareTo(Edge e){ return cost - e.cost;	}
    }
    static class Edge2 implements Comparable<Edge2>
    {
        int node, cost;
        ArrayList<Integer>way;

        Edge2(int a, int b,ArrayList<Integer>z) {
            way=z;
            node = a;	cost = b;
            way.add(node+1);
        }

        public int compareTo(Edge2 e){ return cost - e.cost;	}
    }
}