CF2252C.Risky Tower

You are playing a 2D Jenga game represented by a grid with $n$ rows and $m$ columns. The $1$-st row is the top level of the tower, and the $n$-th row is the bottom level.

Each piece at row $i$ and column $j$ has a destabilization factor $a_{i,j}$. Additionally, each row $i$ has an initial stability index of $v_i$.

When you remove a piece, it is completely discarded from the game. Removing a piece from row $i$ damages all levels at and above it. Specifically, for every row $k$ such that $1 \le k \le i$, its stability index is decreased by $a_{i,j}$.

The tower collapses if either of the following conditions is met:

• The stability index of any level drops to $0$ or less.
• Any level is left with exactly $0$ pieces (even if it is the topmost level).

Find the minimum number of pieces you must remove such that the tower collapses.

你正在玩一个由 $n$ 行 $m$ 列网格表示的二维叠叠乐（Jenga）游戏。第 $1$ 行是塔的最顶层，第 $n$ 行是塔的最底层。

位于第 $i$ 行、第 $j$ 列的每一块积木具有一个失稳因子 $a_{i,j}$。此外，每一行 $i$ 具有一个初始稳定性指数 $v_i$。

当你移除一块积木时，它将被完全从游戏中丢弃。移除第 $i$ 行的一块积木会对第 $i$ 行及所有其上方的层级造成损害。具体而言，对每个满足 $1 \le k \le i$ 的行 $k$，其稳定性指数均减少 $a_{i,j}$。

当满足以下任一条件时，塔即倒塌：

• 任一层级的稳定性指数降至 $0$ 或更低；
• 任一层级剩余积木数量恰好为 $0$（即使该层是最顶层）。

求使塔倒塌所需移除的最少积木数量。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$) — the number of rows and columns of the tower.

The second line contains $n$ integers $v_1, v_2, \ldots, v_n$ ($1 \le v_i \le 10^9$) — the initial stability indices of each level from top to bottom.

Each of the next $n$ lines contains $m$ integers. The $j$-th integer on the $i$-th line is $a_{i, j}$ ($1 \le a_{i, j} \le 10^9$) — the destabilization factor of the piece at row $i$ and column $j$.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^6$）—— 分别表示塔的行数与列数。

第二行包含 $n$ 个整数 $v_1, v_2, \ldots, v_n$（$1 \le v_i \le 10^9$）—— 表示从顶层到底层每一层的初始稳定性指数。

接下来的 $n$ 行中，每行包含 $m$ 个整数。第 $i$ 行的第 $j$ 个整数为 $a_{i, j}$（$1 \le a_{i, j} \le 10^9$）—— 表示第 $i$ 行第 $j$ 列方块的失稳因子。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

For each test case, output a single integer — the minimum number of pieces that must be removed to collapse the tower.

对于每个测试用例，输出一个整数——即为使塔倒塌所需移除的最少方块数量。

In the first testcase, we have a $2 \times 3$ tower. The initial stabilities are $v_1 = 10$ and $v_2 = 20$. The top level ($i=1$) has pieces with destabilization factors $2, 2, 2$. The bottom level ($i=2$) has pieces $5, 5, 5$.

If we remove two pieces from the bottom level, it inflicts $5 + 5 = 10$ damage to level $2$, and $5 + 5 = 10$ damage to level $1$. The remaining stability of level $1$ becomes $10 - 10 = 0$. Since its stability dropped to $\le 0$, the tower collapses. Thus, the minimum number of pieces we must remove is $2$.

In the second testcase, $m = 1$. The rule states that the tower collapses if any level is left with exactly $0$ pieces. Since every level initially has $1$ piece, removing any $1$ piece from the tower will instantly empty a level and cause a collapse. Therefore, the minimum number of pieces to remove is $1$.

在第一个测试用例中，我们有一个 $2 \times 3$ 的塔。初始稳定性分别为 $v_1 = 10$ 和 $v_2 = 20$。顶层（$i=1$）的方块具有失稳因子 $2, 2, 2$；底层（$i=2$）的方块失稳因子为 $5, 5, 5$。

如果我们从底层移除两个方块，则会对第 $2$ 层造成 $5 + 5 = 10$ 点伤害，同时也会对第 $1$ 层造成 $5 + 5 = 10$ 点伤害。第 $1$ 层剩余的稳定性变为 $10 - 10 = 0$。由于其稳定性已降至 $\le 0$，塔将倒塌。因此，我们必须移除的最少方块数为 $2$。

在第二个测试用例中，$m = 1$。规则规定：若任一层恰好剩下 $0$ 个方块，则塔将倒塌。由于每一层初始均有 $1$ 个方块，因此只要从塔中移除任意 $1$ 个方块，就会立即清空某一层并导致倒塌。故需移除的最少方块数为 $1$。