{"raw_statement":[{"iden":"statement","content":"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.\n\nIf $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.\n\nThe 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.\n\nDetermine 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)."},{"iden":"input","content":"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.\n\nThe 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."},{"iden":"output","content":"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_."},{"iden":"examples","content":"Input\n\n3 5\n2 1 -3\n\nOutput\n\n3\n\nInput\n\n2 4\n-1 1\n\nOutput\n\n4\n\nInput\n\n4 10\n2 4 1 2\n\nOutput\n\n2"},{"iden":"note","content":"In the first example initially in the bus could be $0$, $1$ or $2$ passengers.\n\nIn the second example initially in the bus could be $1$, $2$, $3$ or $4$ passengers.\n\nIn the third example initially in the bus could be $0$ or $1$ passenger."}],"translated_statement":[{"iden":"statement","content":"伯兰的公交车配备了视频监控系统。该系统记录公交车在每站上下车后乘客数量的变化。\n\n如果在当前公交站之前车上有 $x$ 名乘客，在当前公交站之后车上有 $y$ 名乘客，则系统记录数值 $y - x$。因此，系统记录显示了乘客数量的变化情况。\n\n对一辆公交车进行了 $n$ 个公交站的测试运行。因此，系统记录了一个整数序列 $a_1, a_2, dots.h, a_n$（每个公交站恰好一个数值），其中 $a_i$ 是第 $i$ 个公交站的记录。公交站按时间顺序编号为 $1$ 到 $n$。\n\n确定在第一个公交站之前车上有多少名乘客的可能方式数，假设公交车的容量为 $w$（即在任何时刻，车上的乘客数必须在 $0$ 到 $w$ 之间，包含端点）。\n\n第一行包含两个整数 $n$ 和 $w$ $(1 lt.eq n lt.eq 1 thin 000, 1 lt.eq w lt.eq 10^9)$ —— 公交站数量和公交车容量。\n\n第二行包含一个序列 $a_1, a_2, dots.h, a_n$ $(-10^6 lt.eq a_i lt.eq 10^6)$，其中 $a_i$ 表示第 $i$ 个公交站后视频系统记录的数值。\n\n请输出在第一个公交站之前车上有多少名乘客的可能方式数，假设公交车容量为 $w$。如果情况矛盾（即无论初始乘客数是多少都会产生矛盾），请输出 _0_。\n\n在第一个例子中，初始时车上有 $0$、$1$ 或 $2$ 名乘客。\n\n在第二个例子中，初始时车上有 $1$、$2$、$3$ 或 $4$ 名乘客。\n\n在第三个例子中，初始时车上有 $0$ 或 $1$ 名乘客。\n\n"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $w$ $(1 lt.eq n lt.eq 1 thin 000, 1 lt.eq w lt.eq 10^9)$ —— 公交站数量和公交车容量。第二行包含一个序列 $a_1, a_2, dots.h, a_n$ $(-10^6 lt.eq a_i lt.eq 10^6)$，其中 $a_i$ 表示第 $i$ 个公交站后视频系统记录的数值。"},{"iden":"output","content":"请输出在第一个公交站之前车上有多少名乘客的可能方式数，假设公交车容量为 $w$。如果情况矛盾（即无论初始乘客数是多少都会产生矛盾），请输出 _0_。"},{"iden":"examples","content":"输入\n3 5\n2 1 -3\n输出\n3\n\n输入\n2 4\n-1 1\n输出\n4\n\n输入\n4 10\n2 4 1 2\n输出\n2"},{"iden":"note","content":"在第一个例子中，初始时车上有 $0$、$1$ 或 $2$ 名乘客。在第二个例子中，初始时车上有 $1$、$2$、$3$ 或 $4$ 名乘客。在第三个例子中，初始时车上有 $0$ 或 $1$ 名乘客。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of bus stops.  \nLet $ w \\in \\mathbb{Z}^+ $ be the bus capacity.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of passenger changes at each stop, where $ a_i \\in \\mathbb{Z} $ is the net change after stop $ i $.  \n\nLet $ x_0 \\in \\mathbb{Z} $ be the initial number of passengers before the first stop.  \nFor $ i \\in \\{1, \\dots, n\\} $, define $ x_i = x_0 + \\sum_{j=1}^i a_j $ as the number of passengers after stop $ i $.\n\n**Constraints**  \n1. $ 0 \\le x_0 \\le w $  \n2. For all $ i \\in \\{0, 1, \\dots, n\\} $: $ 0 \\le x_i \\le w $\n\nDefine the prefix sums:  \nLet $ s_0 = 0 $, and for $ i \\in \\{1, \\dots, n\\} $, let $ s_i = \\sum_{j=1}^i a_j $.  \nThen $ x_i = x_0 + s_i $.\n\nThus, the constraints become:  \nFor all $ i \\in \\{0, 1, \\dots, n\\} $:  \n$$\n0 \\le x_0 + s_i \\le w\n$$\n\nRewriting:  \n$$\n- s_i \\le x_0 \\le w - s_i \\quad \\text{for all } i \\in \\{0, 1, \\dots, n\\}\n$$\n\nDefine:  \n$$\nL = \\max_{i \\in \\{0, \\dots, n\\}} (-s_i), \\quad U = \\min_{i \\in \\{0, \\dots, n\\}} (w - s_i)\n$$\n\n**Objective**  \nCompute the number of integer values $ x_0 \\in \\mathbb{Z} $ satisfying:  \n$$\n\\max(0, L) \\le x_0 \\le \\min(w, U)\n$$\n\nIf $ \\max(0, L) > \\min(w, U) $, output $ 0 $.  \nOtherwise, output $ \\min(w, U) - \\max(0, L) + 1 $.","simple_statement":null,"has_page_source":false}