CF1936C.Pokémon Arena

You are at a dueling arena. You also possess $n$ Pokémons. Initially, only the $1$-st Pokémon is standing in the arena.

Each Pokémon has $m$ attributes. The $j$-th attribute of the $i$-th Pokémon is $a_{i,j}$. Each Pokémon also has a cost to be hired: the $i$-th Pokémon's cost is $c_i$.

You want to have the $n$-th Pokémon stand in the arena. To do that, you can perform the following two types of operations any number of times in any order:

• Choose three integers $i$, $j$, $k$ ($1 \le i \le n$, $1 \le j \le m$, $k \gt 0$), increase $a_{i,j}$ by $k$ permanently. The cost of this operation is $k$.
• Choose two integers $i$, $j$ ($1 \le i \le n$, $1 \le j \le m$) and hire the $i$-th Pokémon to duel with the current Pokémon in the arena based on the $j$-th attribute. The $i$-th Pokémon will win if $a_{i,j}$ is greater than or equal to the $j$-th attribute of the current Pokémon in the arena (otherwise, it will lose). After the duel, only the winner will stand in the arena. The cost of this operation is $c_i$.

Find the minimum cost you need to pay to have the $n$-th Pokémon stand in the arena.

你身处一个决斗竞技场。你拥有 $n$ 只宝可梦。初始时，只有第 $1$ 只宝可梦站在竞技场中。

每只宝可梦有 $m$ 项属性。第 $i$ 只宝可梦的第 $j$ 项属性为 $a_{i,j}$。每只宝可梦还有一个雇佣成本：第 $i$ 只宝可梦的成本为 $c_i$。

你的目标是让第 $n$ 只宝可梦最终站在竞技场中。为此，你可以以任意顺序、任意次数执行以下两类操作：

• 选择三个整数 $i$、$j$、$k$（满足 $1 \le i \le n$，$1 \le j \le m$，$k > 0$），将 $a_{i,j}$ 永久增加 $k$。该操作的成本为 $k$。
• 选择两个整数 $i$、$j$（满足 $1 \le i \le n$，$1 \le j \le m$），雇佣第 $i$ 只宝可梦，使其基于第 $j$ 项属性与当前在竞技场中的宝可梦进行决斗。若第 $i$ 只宝可梦的第 $j$ 项属性 $a_{i,j}$ 大于或等于当前竞技场中宝可梦的第 $j$ 项属性，则第 $i$ 只宝可梦获胜（否则失败）。决斗结束后，仅胜者留在竞技场中。该操作的成本为 $c_i$。

求使第 $n$ 只宝可梦最终站在竞技场中所需支付的最小总成本。

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

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 4 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$, $2 \leq n \cdot m \leq 4 \cdot 10^5$).

The second line of each test case contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 10^9$).

The $i$-th of the following $n$ lines contains $m$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$ ($1 \le a_{i,j} \le 10^9$).

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

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 4 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$，$2 \leq n \cdot m \leq 4 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 10^9$）。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$（$1 \le a_{i,j} \le 10^9$）。

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

For each test case, output the minimum cost to make the $n$-th Pokémon stand in the arena.

对于每个测试用例，输出使第 $n$ 只宝可梦站在竞技场中的最小代价。

In the first test case, the attribute array of the $1$-st Pokémon (which is standing in the arena initially) is $[2,9,9]$.

In the first operation, you can choose $i=3$, $j=1$, $k=1$, and increase $a_{3,1}$ by $1$ permanently. Now the attribute array of the $3$-rd Pokémon is $[2,2,1]$. The cost of this operation is $k = 1$.

In the second operation, you can choose $i=3$, $j=1$, and hire the $3$-rd Pokémon to duel with the current Pokémon in the arena based on the $1$-st attribute. Since $a_{i,j}=a_{3,1}=2 \ge 2=a_{1,1}$, the $3$-rd Pokémon will win. The cost of this operation is $c_3 = 1$.

Thus, we have made the $3$-rd Pokémon stand in the arena within the cost of $2$. It can be proven that $2$ is minimum possible.

In the second test case, the attribute array of the $1$-st Pokémon in the arena is $[9,9,9]$.

In the first operation, you can choose $i=2$, $j=3$, $k=2$, and increase $a_{2,3}$ by $2$ permanently. Now the attribute array of the $2$-nd Pokémon is $[6,1,9]$. The cost of this operation is $k = 2$.

In the second operation, you can choose $i=2$, $j=3$, and hire the $2$-nd Pokémon to duel with the current Pokémon in the arena based on the $3$-rd attribute. Since $a_{i,j}=a_{2,3}=9 \ge 9=a_{1,3}$, the $2$-nd Pokémon will win. The cost of this operation is $c_2 = 3$.

In the third operation, you can choose $i=3$, $j=2$, and hire the $3$-rd Pokémon to duel with the current Pokémon in the arena based on the $2$-nd attribute. Since $a_{i,j}=a_{1,2}=2 \ge 1=a_{2,2}$, the $3$-rd Pokémon can win. The cost of this operation is $c_3 = 1$.

Thus, we have made the $3$-rd Pokémon stand in the arena within the cost of $6$. It can be proven that $6$ is minimum possible.

在第一个测试用例中，初始站在竞技场中的第 $1$ 只宝可梦的属性数组为 $[2,9,9]$。

在第一次操作中，你可以选择 $i=3$、$j=1$、$k=1$，将 $a_{3,1}$ 永久增加 $1$。此时第 $3$ 只宝可梦的属性数组变为 $[2,2,1]$。该操作的代价为 $k = 1$。

在第二次操作中，你可以选择 $i=3$、$j=1$，雇佣第 $3$ 只宝可梦，依据第 $1$ 项属性与当前竞技场中的宝可梦进行对决。由于 $a_{i,j}=a_{3,1}=2 \ge 2=a_{1,1}$，第 $3$ 只宝可梦获胜。该操作的代价为 $c_3 = 1$。

因此，我们以总代价 $2$ 成功使第 $3$ 只宝可梦站在了竞技场中。可以证明 $2$ 是可能的最小代价。

在第二个测试用例中，初始站在竞技场中的第 $1$ 只宝可梦的属性数组为 $[9,9,9]$。

在第一次操作中，你可以选择 $i=2$、$j=3$、$k=2$，将 $a_{2,3}$ 永久增加 $2$。此时第 $2$ 只宝可梦的属性数组变为 $[6,1,9]$。该操作的代价为 $k = 2$。

在第二次操作中，你可以选择 $i=2$、$j=3$，雇佣第 $2$ 只宝可梦，依据第 $3$ 项属性与当前竞技场中的宝可梦进行对决。由于 $a_{i,j}=a_{2,3}=9 \ge 9=a_{1,3}$，第 $2$ 只宝可梦获胜。该操作的代价为 $c_2 = 3$。

在第三次操作中，你可以选择 $i=3$、$j=2$，雇佣第 $3$ 只宝可梦，依据第 $2$ 项属性与当前竞技场中的宝可梦进行对决。由于 $a_{i,j}=a_{1,2}=2 \ge 1=a_{2,2}$，第 $3$ 只宝可梦获胜。该操作的代价为 $c_3 = 1$。

因此，我们以总代价 $6$ 成功使第 $3$ 只宝可梦站在了竞技场中。可以证明 $6$ 是可能的最小代价。