1294: sbjhy想成为pokemon训练大师

$sbjhy$在$pokemon$竞技场上。里面还拥有 $n$宝可梦。最初，只有第一只(1st)宝可梦站在场上。每个宝可梦都有 $m$ 属性。第 $i$个宝可梦的第$j $个属性是$a_{i,j}$ 。 每只宝可梦也有费用：第 $i$ 只宝可梦的费用是 $c_i$。$sbjhy$想让第 $n$ 个宝可梦站在竞技场上。 作为想成为宝可梦训练大师的男人，他拥有强化宝可梦的能力，可以按任意顺序多次执行以下两种类型的操作： 1-选择三个整数 $i$，$j$, $k$( $1≤i≤n$, $1≤j≤m$ , $k>0$ )，将 $a_{i,j}$ 永久增加 $k$。此操作的成本为 $k$。 2-选择两个整数 $i$， $j$ ( $1≤i≤n$ ， $1≤j≤m$ )并根据第 $j$ 个属性，雇佣第 $i$个宝可梦在竞技场中与当前宝可梦决斗。如果 $a_{i,j} $**大于或等于**竞技场中当前神奇宝贝的第 $j$个属性，则第 $i$个宝可梦将获胜(否则，它会输). 决斗结束后，只有胜利者才能站在竞技场上。这次操作的费用是 $c_i$ 。找到您需要支付的最低费用，让第 $n$个神奇宝贝站在竞技场上。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $( 1≤t≤10^5 )$。 测试用例的描述如下。每个测试用例的第一行包含两个整数$n$和$m$($2≤n≤4⋅10^5$ ，$2≤n⋅m≤4⋅10^5$)​。 每个测试用例的第二行包含 $n$ 个整数 $c_1$,$c_2$,…,$c_n$ ( $1≤ci≤10^9 $)​。 下列 $n$ 行中的第 $i$行包含 $m$个整数 $a_{i,1}$,$a_{i,2}$,…,$a_{i,m}$ ( $1≤ai,j≤10^9$ )。 保证所有测试用例的 $n$⋅$m$ 之和不超过 $4⋅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