B4159 [BCSP-X 2024 12 月小学高年级组] 打怪升级

Alice 在玩一个游戏，游戏共有 $n$ 个关卡，你需要操作 $1$ 个主角过关，主角有 $2$ 个属性： 1. 血量 2. 等级 每关的 Boss 会对主角造成伤害（血量减小），第 $i$ 关的 Boss 对等级为 $j$ 的主角造成的伤害值为 $b[i][j]$。 每关打完 Boss 后，在进入下一关前会得到一本经验书，你有 $2$ 个选择： 1. 回血：第 $i$ 关的经验书可以使血量增加 $a[i]$。 2. 改变等级：若假设主角当前等级为 now，使用经验书可以将等级变为 $[1, now + 1]$ 中的任意值。 你需要在 $2$ 个选择中择一执行。 已知主角的初始血量为 $m$，初始等级为 $1$，游戏过程中任意时刻血量必须 $>0$。 现在请问，在通过第 $k$ 个关卡之后（可以使用第 $k$ 关的经验书），主角能达到的最大等级是多少？如果无法通过第 $k$ 关，答案为 0。 请你输出 $k = 1 \sim n$ 的所有答案，注意这 $n$ 个询问是独立的。 例如 $n = 3, m = 2, a = [2, 1, 1]$ $$b[1][1] = 1$$ $$b[2][1] = 2, b[2][2] = 3$$ $$b[3][1] = 3, b[3][2] = 3, b[3][3] = 3$$ - 当 $k = 1$ 时，第一关血量先减为 $2 - 1 = 1$，然后选择升为 2 级，答案为 $2$。 - 当 $k = 2$ 时，第一关血量先减为 $2 - 1 = 1$，然后选择加血 $1 + 2 = 3$；第二关血量减为 $3 - 2 = 1$，然后选择升为 $2$ 级，答案为 $2$。 - 当 $k = 3$ 时，无论如何选择都无法通过第 3 关，答案为 $0$。

第一行 $2$ 个整数 $n, m$，代表关卡数量和初始血量。 第二行 $n$ 个整数 $a[1 \sim n]$ 代表每关经验书的加血量。 接下来 $n$ 行，第 $i$ 行包含 $i$ 个整数代表第 $i$ 关的 Boss 对等级为 $1 \sim i$ 的主角造成的伤害值。

输出 $n$ 行，第 $i$ 行包含 $1$ 个整数代表通过第 $i$ 个关卡之后，主角能达到的最大等级。

### 样例 3-5 见附件。 ### 数据范围 对于所有数据，$1 \leq n \leq 1500, 0 \leq a[i], b[i][j] \leq 100, 1 \leq m \leq 1500$ 本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。 | 子任务编号 | 分值 | $n$ | 子任务依赖 | |:----------:|:----:|:-------:|:------------:| | 1 | 39 | $\leq 10$ | | | 2 | 43 | $\leq 100$ | 1 | | 3 | 18 | $\leq 1500$ | 1,2 |