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)$$$ в ячейку $$$(i, j)$$$ записывается целое число $$$a_{i, j}$$$.

Изначально вы находитесь в ячейке $$$(1, 1)$$$ и хотите попасть в ячейку $$$(n, m)$$$. Вы можете двигаться только вниз или вправо. То есть, если вы находитесь в $$$(i, j)$$$, вы можете перейти только в $$$(i+1, j)$$$ или $$$(i, j+1)$$$ (если соответствующая ячейка существует).

Прежде чем начать движение, вы можете выполнить следующую операцию любое количество раз:

  • Выберите целое число $$$i$$$ от $$$1$$$ до $$$n$$$ и циклически сдвиньте строку $$$i$$$ влево на $$$1$$$. Формально, клеткам $$$a_{i,j}$$$ для всех целых $$$j$$$ ($$$1 \le j \le m$$$) одновременно устанавливается значение $$$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)$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных минимальная стоимость $$$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$$$.