CF2025D.Attribute Checks

想象一个游戏，你扮演的角色有两个属性：“力量”和“智力”，初始时这两个属性的等级都是零。

在游戏过程中，你会获得 $m$ 个属性点，每个属性点可以让你将任意一个属性提升一级。但有时你会遇到所谓的“属性检测”：如果你对应的属性足够高，你就能通过，否则就会失败。

经过一番努力，你终于整理出了一份包含所有获得属性点和遇到检测的完整记录清单。现在你想知道：如果你合理分配属性点，在一次游戏过程中最多能通过多少次属性检测？

注意，你不能改变记录的顺序。

第一行包含两个整数 $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$，表示获得一个属性点，你可以选择将其加到力量或智力上；
• 如果 $r_i > 0$，表示一次智力检测：如果你的智力等级大于等于 $|r_i|$，则通过；
• 如果 $r_i < 0$，表示一次力量检测：如果你的力量等级大于等于 $|r_i|$，则通过。

输入数据还保证：序列 $r_1, r_2, \dots, r_n$ 中恰好有 $m$ 个元素等于 $0$。

输出一个整数，表示你最多能通过多少次属性检测。

在第一个样例中，最优策略是每个点都加到力量上，这样会失败 $2$ 次智力检测，但能通过 $3$ 次力量检测。

在第二个样例中，你会错过所有检测，因为第一个属性点是在检测之后获得的。

在第三个样例中，一种最优策略如下：

1. 第一个点加到智力上；
2. 第二个点加到力量上；
3. 第三个点加到力量上；

这样你能通过 $2$ 次智力检测（$r_3$ 和 $r_9$）和 $2$ 次力量检测（$r_7$ 和 $r_8$）。

由 ChatGPT 4.1 翻译