CF2049D Shift + Esc

对于被某个装置捉弄之后，龙 Evirir 决定利用他的魔法技能来改变现实以迅速逃脱。 你得到一个 $n$ 行 $m$ 列的非负整数网格，以及一个整数 $k$。我们用 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的单元格（$1 \le i \le n$，$1 \le j \le m$）。在每个单元格 $(i, j)$ 上都有一个整数 $a_{i, j}$。 你起始位于 $(1, 1)$，目标是走到 $(n, m)$。在移动过程中，你只能向下或向右移动——也就是说，如果你在 $(i, j)$，只能移动到 $(i+1, j)$ 或 $(i, j+1)$，当然，前提是这些目标单元格必须存在。 在开始移动之前，你可以进行以下操作任意多次： - 从 $1$ 到 $n$ 中选择一个整数 $i$，然后将第 $i$ 行的元素循环左移一位。这个操作的效果是，将每个 $a_{i,j}$ 更新为 $a_{i,(j \bmod m) + 1}$。 请注意，一旦你开始移动，就不能再进行行移操作。从 $(1, 1)$ 到 $(n, m)$ 之后，令 $x$ 是你在开始移动之前进行的操作次数，而 $y$ 是你经过的所有单元格上的整数之和（包括起始和目标位置）。最终成本被定义为 $kx + y$。 你的任务是计算出以最小成本从 $(1, 1)$ 移动到 $(n, m)$ 所需的操作次数。

输入包括多个测试用例。第一行为测试用例数量 $t$（$1 \le t \le 10^4$）。接下来每个测试用例包含： - 一行三个用空格分隔的整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 200$，$0 \leq k \leq 10^9$）。 - 随后的 $n$ 行，每行包含 $m$ 个用空格分隔的整数，分别表示这一行上的 $a_{i,1},\,a_{i,2},\,\ldots,\,a_{i,m}$（$0 \leq a_{i,j} \leq 10^9$）。 所有测试用例中 $n \cdot m$ 的总和不超过 $5 \cdot 10^4$。

对于每个测试用例，输出从起点 $(1, 1)$ 到终点 $(n, m)$ 的最小成本。

在第一个测试用例中，最低成本是 $113$，可以通过以下步骤实现： 1. 将第 3 行循环左移一次。网格变成： $$ \begin{bmatrix} 3 & 4 & 9 \\ 5 & 2 & 4 \\ 101 & 101 & 0 \end{bmatrix}. $$ 2. 按以下路径行进：$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$。 进行了一次操作，访问的路径上整数之和为 $y = 3 + 4 + 2 + 4 + 0 = 13$。因此，总成本为 $kx + y = 100 \cdot 1 + 13 = 113$。 在第二个测试用例中，你可以将第 1 行左移一次，第 2 行左移两次，第 3 行左移三次。最终网格变成： $$ \begin{bmatrix} 0 & 0 & 10 & 10 \\ 10 & 0 & 0 & 0 \\ 10 & 10 & 10 & 0 \end{bmatrix}. $$ 共进行了 $x = 6$ 次操作，并且经过的路径上整数之和为 $y = 0$。因此，总成本为 $6 \cdot 1 + 0 = 6$。 **本翻译由 AI 自动生成**