← 返回题目列表

Codeforces · 978/E

E. 公交车视频系统

中文机器翻译题面 查看原题

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$$$ 乘客。