CF1936C Pokémon 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$ 个属性进行对战。如果 $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 \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$ 行，每行包含 $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$ 只宝可梦站在竞技场上的最小费用。

在第一个测试数据中，最初站在竞技场上的第 $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_{3,1}=2 \ge 2=a_{1,1}$，第 $3$ 只宝可梦获胜。该操作费用为 $c_3=1$。 因此，总费用为 $2$，且可以证明 $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_{2,3}=9 \ge 9=a_{1,3}$，第 $2$ 只宝可梦获胜。该操作费用为 $c_2=3$。 第三次操作，你可以选择 $i=3$，$j=2$，雇佣第 $3$ 只宝可梦与当前竞技场宝可梦以第 $2$ 个属性对战。由于 $a_{3,2}=2 \ge 1=a_{2,2}$，第 $3$ 只宝可梦获胜。该操作费用为 $c_3=1$。 因此，总费用为 $6$，且可以证明 $6$ 是最小可能值。 由 ChatGPT 4.1 翻译