CF2252C Risky Tower

你正在玩一个用网格表示的二维积木塔（Jenga）游戏，塔有 $n$ 行 $m$ 列。第 $1$ 行是塔的顶层，第 $n$ 行是底层。 位于第 $i$ 行第 $j$ 列的积木有一个去稳定因子 $a_{i,j}$。此外，每一行 $i$ 初始有一个稳定指数 $v_i$。 当你移除一块积木时，该积木会被完全移除出游戏。移除第 $i$ 行的一颗积木会对该行及其上方所有行产生影响。具体地，对于每一个第 $k$ 行（$1 \leq k \leq i$），它的稳定指数会减少 $a_{i,j}$。 当满足以下任一条件时，积木塔就会倒塌： - 任何一层的稳定指数降至 $0$ 或以下； - 任何一层积木数恰好为 $0$（哪怕是顶层）。 请你求出至少移除多少个积木可以让积木塔倒塌。

每组测试数据包含多个测试用例。第一行包含测试用例个数 $t$（$1 \leq t \leq 10^4$）。接下来依次描述每组测试用例。 每组测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^6$），表示积木塔的行数和列数。 第二行包含 $n$ 个整数 $v_1,v_2,\ldots,v_n$（$1 \leq v_i \leq 10^9$），表示从顶到下每层的初始稳定指数。 接下来有 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行的第 $j$ 个数为 $a_{i,j}$（$1 \leq a_{i,j} \leq 10^9$），表示该位置的去稳定因子。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示使积木塔倒塌所需移除的最少积木数。

在第一个样例中，这是一个 $2\times3$ 的积木塔，初始稳定指数为 $v_1=10$、$v_2=20$。顶层（$i=1$）的去稳定因子为 $2,2,2$。底层（$i=2$）的去稳定因子为 $5,5,5$。 如果我们从底层移除两块积木，会对第 $2$ 行造成 $5+5=10$ 的损伤，对第 $1$ 行也造成 $5+5=10$ 的损伤。顶层剩余的稳定指数为 $10-10=0$，小于等于 $0$，因而积木塔倒塌。因此，最少只需移除 $2$ 块积木。 在第二个样例中，$m=1$。因为规则规定若任一层积木为 $0$ 块则立刻塌塔，而每层只有 $1$ 块积木。只需移除任意 $1$ 块积木即可导致某一层为空，从而倒塌。因此，本例答案为 $1$。 由 ChatGPT 5 翻译