在玩弄某种装置并被抓住后,龙 Evirir 决定充分利用他们的魔法技能 - 扭曲现实以快速逃脱!
给定一个网格,其中包含非负整数 $$$n$$$ 行和 $$$m$$$ 列以及整数 $$$k$$$。令 $$$(i, j)$$$ 表示从顶部算起第 $$$i$$$ 行和从左边算起第 $$$j$$$ 列中的单元格 ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$)。对于每个单元格 $$$(i, j)$$$,整数 $$$a_{i, j}$$$ 写入单元格 $$$(i, j)$$$ 上。
您最初位于 $$$(1, 1)$$$,并且想要前往 $$$(n, m)$$$。您只能向下或向右移动。也就是说,如果您位于$$$(i, j)$$$,则只能移动到$$$(i+1, j)$$$ 或$$$(i, j+1)$$$(如果对应的单元格存在)。
在开始移动之前,您可以多次执行以下操作:
- 选择 $$$1$$$ 和 $$$n$$$ 之间的整数 $$$i$$$ 并将行 $$$i$$$ 循环向左移动 $$$1$$$。形式上,对于所有整数 $$$j$$$ ($$$1 \le j \le m$$$),同时将 $$$a_{i,j}$$$ 设置为 $$$a_{i,(j \bmod m) + 1}$$$。
从 $$$(1, 1)$$$ 移动到 $$$(n, m)$$$ 后,令 $$$x$$$ 为移动前执行的操作数,令 $$$y$$$ 为写入到访问过的单元格上的整数之和(包括 $$$(1, 1)$$$ 和 $$$(n, m)$$$)。那么成本定义为$$$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$$$ 行。第 $$$i$$$ 行包含 $$$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)$$$ 的最小成本。
示例
输入 #1
5 3 3 100 3 4 9 5 2 4 0 101 101 3 4 1 10 0 0 10 0 0 10 0 10 10 0 10 1 1 3 4 3 2 3 1 2 3 6 5 4 10 10 14 58 49 25 12 89 69 8 49 71 23 45 27 65 59 36 100 73 23 5 84 82 91 54 92 53 15 43 46 11 65 61 69 71 87 67 72 51 42 55 80 1 64 8 54 61 70 47 100 84 50 86 93 43 51 47 35 56 20 33 61 100 59 5 68 15 55 69 8 8 60 33 61 20 79 69 51 23 24 56 28 67 76 3 69 58 79 75 10 65 63 6 64 73 79 17 62 55 53 61 58
输出 #1
113 6 4 13 618
注意
在第一个测试用例中,最低成本 $$$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)$$$。
$$$x = 1$$$ 操作在移动之前完成。访问过的单元格上的整数之和为 $$$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$$$。