Berland 的公交车配备了视频监控系统。系统记录公交车停站后乘客人数变化的信息。
如果 $$$x$$$ 是当前公交车站之前公交车上的乘客人数,而 $$$y$$$ 是当前公交车站之后公交车上的乘客人数,则系统记录数字 $$$y-x$$$。所以系统记录显示了乘客数量的变化情况。
测试运行针对单个公交车和 $$$n$$$ 公交车站。因此,系统记录了整数序列$$$a_1, a_2, \dots, a_n$$$(每个公交车站只有一个数字),其中$$$a_i$$$是公交车站$$$i$$$的记录。巴士站按时间顺序编号为 $$$1$$$ 至 $$$n$$$。
如果公交车的载客量等于 $$$w$$$(也就是说,公交车上任何时候都应该有从 $$$0$$$ 到 $$$w$$$ 的乘客,请确定在第一个公交车站之前公交车上可能有多少人。
输入
第一行包含两个整数 $$$n$$$ 和 $$$w$$$ $$$(1 \le n \le 1\,000, 1 \le w \le 10^{9})$$$ — 公交车站数量和公交车容量。
第二行包含序列 $$$a_1, a_2, \dots, a_n$$$ $$$(-10^{6} \le a_i \le 10^{6})$$$,其中 $$$a_i$$$ 等于第 $$$i$$$ 个公交车站后视频系统记录的数字。
输出
如果公交车的载客量等于 $$$w$$$,则打印第一个公交车站之前公交车上可能有多少人的可能方式数。如果情况矛盾(即对于任何初始乘客数量都会存在矛盾),则打印 0。
示例
输入 #1
3 5 2 1 -3
输出 #1
3
输入 #2
2 4 -1 1
输出 #2
4
输入 #3
4 10 2 4 1 2
输出 #3
2
注意
在第一个示例中,最初在公共汽车上的乘客可能是 $$$0$$$、$$$1$$$ 或 $$$2$$$ 乘客。
在第二个示例中,最初在公共汽车上的乘客可能是$$$1$$$、$$$2$$$、$$$3$$$ 或$$$4$$$ 乘客。
在第三个示例中,最初在公共汽车上的乘客可能是 $$$0$$$ 或 $$$1$$$ 乘客。