CF2049D Shift + Esc

After having fun with a certain contraption and getting caught, Evirir the dragon decides to put their magical skills to good use — warping reality to escape fast! You are given a grid with $ n $ rows and $ m $ columns of non-negative integers and an integer $ k $ . Let $ (i, j) $ denote the cell in the $ i $ -th row from the top and $ j $ -th column from the left ( $ 1 \le i \le n $ , $ 1 \le j \le m $ ). For every cell $ (i, j) $ , the integer $ a_{i, j} $ is written on the cell $ (i, j) $ . You are initially at $ (1, 1) $ and want to go to $ (n, m) $ . You may only move down or right. That is, if you are at $ (i, j) $ , you can only move to $ (i+1, j) $ or $ (i, j+1) $ (if the corresponding cell exists). Before you begin moving, you may do the following operation any number of times: - Choose an integer $ i $ between $ 1 $ and $ n $ and cyclically shift row $ i $ to the left by $ 1 $ . Formally, simultaneously set $ a_{i,j} $ to $ a_{i,(j \bmod m) + 1} $ for all integers $ j $ ( $ 1 \le j \le m $ ). Note that you may not do any operation after you start moving.After moving from $ (1, 1) $ to $ (n, m) $ , let $ x $ be the number of operations you have performed before moving, and let $ y $ be the sum of the integers written on visited cells (including $ (1, 1) $ and $ (n, m) $ ). Then the cost is defined as $ kx + y $ . Find the minimum cost to move from $ (1, 1) $ to $ (n, m) $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line contains three space-separated integers $ n $ , $ m $ , and $ k $ ( $ 1 \leq n, m \leq 200 $ , $ 0 \leq k \leq 10^9 $ ). Then, $ n $ lines follow. The $ i $ -th line contains $ m $ space-separated integers, $ a_{i,1},\,a_{i,2},\,\ldots,\,a_{i,m} $ ( $ 0 \leq a_{i,j} \leq 10^9 $ ). It is guaranteed that the sum of $ n \cdot m $ over all test cases does not exceed $ 5 \cdot 10^4 $ .

For each test case, output a single integer, the minimum cost to move from $ (1, 1) $ to $ (n, m) $ .

In the first test case, the minimum cost of $ 113 $ can be achieved as follows: 1. Cyclically shift row 3 once. The grid now becomes $ $$$\begin{bmatrix}3 & 4 & 9\\5 & 2 & 4\\101 & 101 & 0\end{bmatrix}. $ $

Move as follows: $ (1, 1) \\to (1, 2) \\to (2, 2) \\to (2, 3) \\to (3, 3) $ .

$ x = 1 $ operation is done before moving. The sum of integers on visited cells is $ y = 3 + 4 + 2 + 4 + 0 = 13 $ . Therefore, the cost is $ kx + y = 100 \\cdot 1 + 13 = 113 $ .

In the second test case, one can shift row 1 once, row 2 twice, and row 3 thrice. Then, the grid becomes $ $ \begin{bmatrix}0 & 0 & 10 & 10\\10 & 0 & 0 & 0\\10 & 10 & 10 & 0\end{bmatrix}. $ $

$ x = 6 $ operations were done before moving, and there is a path of cost $ y = 0 $ . Therefore, the cost is $ 6 \\cdot 1 + 0 = 6$$$.