D. Shift + Esc

每个测试用例时间限制：$2.5$ 秒 每个测试用例内存限制：$512$ 兆字节

龙埃维里尔在摆弄某个装置被抓后，决定好好运用自己的魔法能力——扭曲现实快速逃离！

给定一个由非负整数组成的 $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 \le i \le n$ 的整数 $i$，将第 $i$ 行循环左移 $1$ 位。 形式化描述：对于所有满足 $1 \le j \le m$ 的整数 $j$，同时令 $a_{i,j} = a_{i,(j \bmod m)+1}$。

注意：你不能在开始移动后执行任何操作。

从 $(1,1)$ 移动到 $(n,m)$ 后：

• 设 $x$ 为移动前执行的总操作次数；
• 设 $y$ 为经过的所有单元格上的整数之和（包含起点 $(1,1)$ 和终点 $(n,m)$）。

则代价定义为：$k \cdot x + y$。

请你求出从 $(1,1)$ 移动到 $(n,m)$ 的最小代价。

输入

每个测试文件包含多组测试用例。

1. 第一行输入测试用例的数量 $t$（$1 \le t \le 10^4$）。
2. 每组测试用例的格式：
   • 第一行输入三个空格分隔的整数 $n, m, k$（$1 \le n,m \le 200$，$0 \le k \le 10^9$）。
   • 接下来 $n$ 行，第 $i$ 行包含 $m$ 个空格分隔的整数 $a_{i,1},a_{i,2},\dots,a_{i,m}$（$0 \le a_{i,j} \le 10^9$）。

保证：所有测试用例的 $n \cdot m$ 之和不超过 $5 \cdot 10^4$。

输出

对于每组测试用例，输出一个整数，表示移动的最小代价。

样例输入

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

样例输出

113
6
4
13
618

样例解释

1. 第一组测试用例 最小代价 $113$ 的获取方式： 将第 $3$ 行循环左移 $1$ 次，网格变为：

   $$\begin{bmatrix} 3 & 4 & 9 \\ 5 & 2 & 4 \\ 101 & 101 & 0 \end{bmatrix} $$

   移动路径：$(1,1) \to (1,2) \to (2,2) \to (2,3) \to (3,3)$。 操作次数 $x=1$，路径和 $y=3+4+2+4+0=13$。 代价：$k \cdot x + y = 100 \cdot 1 + 13 = 113$。

2. 第二组测试用例 对第 $1$ 行左移 $1$ 次、第 $2$ 行左移 $2$ 次、第 $3$ 行左移 $3$ 次，网格变为：

   $$\begin{bmatrix} 0 & 0 & 10 & 10 \\ 10 & 0 & 0 & 0 \\ 0 & 0 & 10 & 10 \end{bmatrix} $$

   操作次数 $x=6$，路径和 $y=0$。 花费：$6 \cdot 1 + 0 = 6$。