题目描述

你在玩一个 2D 层叠积木（Jenga）游戏，该游戏由一个 $n$ 行 $m$ 列的网格表示。第 $1$ 行是积木塔的最顶层，第 $n$ 行是最底层。

位于第 $i$ 行第 $j$ 列的每一块积木都有一个“失稳系数” $a_{i,j}$。此外，每一层 $i$ 都有一个初始的“稳定指数” $v_i$。

当你移除一块积木时，它将从游戏中完全被丢弃。从第 $i$ 行移除一块积木，会对该层及以上的所有层造成破坏。具体来说，对于每一个满足 $1 \le k \le i$ 的行 $k$，其稳定指数都会减去 $a_{i,j}$。

如果满足以下任一条件，积木塔就会倒塌：

1. 任何一层的稳定指数降至 $0$ 或 $0$ 以下。
2. 任何一层的积木数量恰好变为 $0$ 块（即使是最顶层）。

请找出导致积木塔倒塌所必须移除的最少积木数量。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^6$）—— 积木塔的行数和列数。
• 第二行包含 $n$ 个整数 $v_1, v_2, \dots, 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$ 列积木的失稳系数。

输出格式

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

样例输入 1

2
2 3
10 20
2 2 2
5 5 5
3 1
100 100 100
1
2
3

样例输出 1

2
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$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $1 \le n, m \le 10^6$。
• 保证同一测试点内所有测试用例的 $n \times m$ 之和不超过 $10^6$。
• 对于所有测试点，保证 $1 \le v_i, a_{i,j} \le 10^9$。
• 保证所有的输入数值均为整数。