题目描述

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]$

• 当 $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 2
2 1 1
1
2 3
3 3 3

2
2
0

10 98
67 100 76 15 44 86 38 95 5 8
43
25 91
14 18 24
79 79 60 85
35 47 59 22 96
53 78 43 95 55 25
74 26 97 30 42 14 6
100 70 79 49 83 74 43 38
64 38 75 79 59 10 54 17 2
34 19 19 4 23 90 99 97 93 10

2
2
3
4
4
4
5
5
5
6

提示

样例 3-5

见附件。

数据范围

对于所有数据，$1 \leq n \leq 1500, 0 \leq a[i], b[i][j] \leq 100, 1 \leq m \leq 1500$

本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。