属性检查 - 代码源竞赛平台

题目描述

蜗蜗正在进行一场冒险，他的力量和智力初始都为 $0$。冒险过程中有 $n$ 条记录，第 $i$ 条记录用整数 $r_i$ 表示，需要按照给定的顺序依次处理：

• 如果 $r_i=0$，蜗蜗获得一个属性点，必须立即将力量或智力中的一项增加 $1$；
• 如果 $r_i>0$，蜗蜗接受一次智力检查。当前智力不小于 $r_i$ 时，可以通过检查；
• 如果 $r_i<0$，蜗蜗接受一次力量检查。当前力量不小于 $-r_i$ 时，可以通过检查。

无论是否通过检查，都要继续处理后面的记录。检查不会消耗属性，也不能改变记录的处理顺序。所有记录中恰好有 $m$ 条记录的值为 $0$。

请你求出蜗蜗最多能够通过多少次检查。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示记录数量和能够获得的属性点数量。

第二行包含 $n$ 个整数 $r_1,r_2,\ldots,r_n$，依次表示每条记录的内容。

输出格式

输出一行一个整数，表示最多能够通过的检查次数。

样例

6 2
0 1 -1 0 2 -1

2

样例解释

一种最优方案是将第一个属性点加给智力，将第二个属性点加给力量。

这样可以通过第 $2$ 条记录中的智力检查和第 $6$ 条记录中的力量检查，共通过 $2$ 次检查。

数据范围

对于 100% 的数据，保证 $1\le m\le 5000$，$m<n\le 2\times 10^6$，$-m\le r_i\le m$，且恰好有 $m$ 个 $r_i=0$。