每次测试的时间限制：$3$ 秒
每次测试的内存限制：$512$ 兆字节

你身处一个决斗竞技场。你拥有 $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$ 个属性与当前竞技场中的宝可梦进行决斗。如果 $a_{i,j}$ 大于或等于 当前竞技场中宝可梦的第 $j$ 个属性，则第 $i$ 只宝可梦获胜（否则失败）。决斗后，只有获胜者留在竞技场中。此操作的代价为 $c_i$。

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

输入

每个测试点包含多个测试用例。第一行包含测试用例的数量 $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 \le n \cdot m \le 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$。

输出

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

示例

输入

4  
3 3  
2 3 1  
2 9 9  
6 1 7  
1 2 1  
3 3  
2 3 1  
9 9 9  
6 1 7  
1 2 1  
4 2  
2 8 3 5  
18 24  
17 10  
1 10  
1 1  
6 3  

21412674  3212925  172015806  250849370  306960171  333018900  
950000001  950000001  950000001  
821757276  783362401  760000001  
570000001  700246226  600757652  
380000001  423513575  474035234  
315201473  300580025  287023445  
1 1 1  

输出

2  
6  
17  
1224474550  

注释

在第一个测试用例中，初始站在竞技场中的第 $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$ 是最小可能值。