Во время игры с таинственной установкой дракона Эвирира поймали. Он решил найти хорошее применение своим магическим навыкам — исказить реальность, чтобы быстро сбежать!
Дана клетчатая сетка с \(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)\).
Примечание
В первом наборе входных данных минимальная стоимость \(113\) может быть достигнута следующим образом:
- Циклически сдвиньте строку 3 один раз. Сетка станет равна \(\)\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\). Следовательно, стоимость равна \(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\).