想象一个游戏,您扮演的角色具有两个属性:“力量”和“智力”,最初的等级为零。
在游戏过程中,您将获得 $$$m$$$ 属性点,这些属性点可让您提高属性等级 — 1 点将使其中一项属性提高一级。但有时候,你会遇到所谓的“属性检查”:如果你对应的属性足够高,你就会通过;如果你的属性足够高,你就会通过。否则,你就会失败。
花了一些时间,你终于准备了一份清单,其中包含你获得的所有积分和你所达到的所有检查的记录。现在您想知道:如果您明智地使用积分,一次运行中最多可以通过多少属性检查?
请注意,您无法更改记录的顺序。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le 5000$$$; $$$m < n \le 2 \cdot 10^6$$$) - 列表中的记录数以及您在游戏中获得的总分。
第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$-m \le r_i \le m$$$),其中 $$$r_i$$$ 编码第 $$$i$$$ 条记录:
- 如果$$$r_i = 0$$$,则第$$$i$$$记录为获取一个属性点。您可以花费来升级力量或智力;
- 如果$$$r_i > 0$$$,那么这是一次智力检定:如果你的智力水平大于或等于$$$|r_i|$$$,你就通过了。
- 如果$$$r_i < 0$$$,那么这是一次力量检查:如果你的力量水平大于或等于$$$|r_i|$$$,你就通过了。
输入的附加约束:序列 $$$r_1, r_2, \dots, r_n$$$ 恰好包含等于 $$$0$$$ 的 $$$m$$$ 元素。
输出
打印一个整数 — 您可以通过的最大检查次数。
示例
输入 #1
10 5 0 1 0 2 0 -3 0 -4 0 -5
输出 #1
3
输入 #2
3 1 1 -1 0
输出 #2
0
输入 #3
9 3 0 0 1 0 2 -3 -2 -2 1
输出 #3
4
注意
在第一个测试中,最好将每一点都花在力量上,因此你将无法通过 $$$2$$$ 智力检查,但通过 $$$3$$$ 力量检查。
在第二个测试中,您将无法通过两项检查,因为您获得的第一点是在检查之后。
在第三次测试中,最佳策略之一是:
1.在智力上花费第一点;
2.将第二点花在力量上;
3.将第三点花在力量上;