Pokémon Arena

题目描述

你现在处于一个对战竞技场，并且拥有 $n$ 只宝可梦。最初，只有第 $1$ 只宝可梦站在竞技场上。

每只宝可梦有 $m$ 个属性。第 $i$ 只宝可梦的第 $j$ 个属性为 $a_{i,j}$，雇佣费用为 $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$ 个属性对战。若挑战者的该属性不小于当前宝可梦的该属性，则挑战者获胜；否则当前宝可梦获胜。对战后只有获胜者留在场上。本次雇佣支付 $c_i$ 的费用。

求使第 $n$ 只宝可梦最终站在竞技场上的最小总费用。

输入格式

第一行一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n,m$。
• 第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$。
• 接下来 $n$ 行，每行包含 $m$ 个整数 $a_{i,1},a_{i,2},\ldots,a_{i,m}$。

输出格式

对每组测试数据输出一个整数，表示所求的最小总费用。

样例输入 1

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

样例输出 1

2
6
17
1224474550

样例解释

在第一组数据中，可以先花费 $1$ 将第 $3$ 只宝可梦的第一个属性加到 $2$，再花费 $c_3=1$ 雇佣它挑战第 $1$ 只宝可梦，总费用为 $2$。

数据范围

• $1\le t\le 10^5$；
• $2\le n\le 4\times 10^5$，$1\le m\le 2\times 10^5$；
• $2\le n\cdot m\le 4\times 10^5$；
• $1\le c_i,a_{i,j}\le 10^9$；
• 单个输入文件中所有测试数据的 $n\cdot m$ 之和不超过 $4\times 10^5$。