P15558 [CCPC 2025 Harbin Site] Snow Shoveling.

After a heavy snow, little w needs to clean up his yard so that the uneven snow piles look at least a bit neater. The yard can be seen as an $n \times m$ grid. The cell in row $i$ and column $j$ is covered by snow with relative height $h_{i,j}$. Little w has the following operations to deal with the snow piles: - Choose $1 \le i < n, 1 \le j \le m$, and push the snow pile at row $i$, column $j$ to the next row. This operation decreases $h_{i,j}$ by $1$ and increases $h_{i+1,j}$ by $1$. **This operation has no cost.** - Choose $1 \le i \le n, 1 \le j < m$, and push the snow pile at row $i$, column $j$ to the next column. This operation decreases $h_{i,j}$ by $1$ and increases $h_{i,j+1}$ by $1$. **This operation has no cost.** - Choose $1 \le i \le n, 1 \le j \le m$, and make snow on the pile at row $i$, column $j$. This operation increases $h_{i,j}$ by $1$. This operation costs $1$. - Choose $1 \le i \le n, 1 \le j \le m$, and remove snow from the pile at row $i$, column $j$. This operation decreases $h_{i,j}$ by $1$. This operation costs $1$. Little w wants to perform some operations to make all $h_{i,j}$ equal to $0$, with the minimum total cost. Can you help him compute the minimum cost?

The first line contains an integer $T$ ($1 \le T \le 10^6$), indicating the number of test cases. Then each test case is given as follows: The first line contains two integers $n, m$ ($1 \le n, m \le 10^3$), representing the number of rows and columns of the yard. The next $n$ lines describe the grid. Line $i$ contains $m$ integers $h_{i,1}, h_{i,2}, \ldots, h_{i,m}$ ($-10^9 \le h_{i,j} \le 10^9$), where the $j$-th integer is the relative snow height in the cell at row $i$, column $j$. For all testdata, it is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

For each test case, output one integer per line, representing the minimum cost for little w to reach the goal.

Translated by ChatGPT 5