P10997 [MX-J3-T4] Partition

Original problem link: 。

You are given a matrix with $n$ rows and $m$ columns. The cell in row $i$ and column $j$ (denoted as $(i,j)$) contains an integer $a_{i,j}$. - We say $(a,b)$ is **below** $(c,d)$ if and only if $b=d,a>c$, i.e., **in the same column, the row index is larger**. - We say $(a,b)$ is **above** $(c,d)$ if and only if $(c,d)$ is **below** $(a,b)$. - We say $(a,b)$ is **to the right of** $(c,d)$ if and only if $a=c,b>d$, i.e., **in the same row, the column index is larger**. - We say $(a,b)$ is **to the left of** $(c,d)$ if and only if $(c,d)$ is **to the right of** $(a,b)$. As shown in the figure, below $A(2,2)$ there are $D(3,2),E(4,2)$, and to its right there are $B(2,3),C(2,4)​$.  To make the matrix look nicer, you want to color each cell with one of four colors: red, orange, yellow, and green. There are many possible colorings, but a coloring is called **simple** if it satisfies the following requirements: - For a red cell: cells **above** it can only be red; cells **to the left** can only be red or yellow; cells **to the right** can only be red or orange. - For an orange cell: cells **to the right** can only be orange; cells **above** can only be orange or red; cells **below** can only be orange or green. - For a green cell: cells **below** can only be green; cells **to the right** can only be green or orange; cells **to the left** can only be green or yellow. - For a yellow cell: cells **to the left** can only be yellow; cells **below** can only be yellow or green; cells **above** can only be yellow or red. The figure above shows some possible colorings, where: - The first one is simple. - The second one is also simple. Note that if cells of a certain color do not exist, then you can directly ignore the corresponding requirements. - The third one is not simple, because for the green cell $F(3,2)$, the cell below it $G(4,2)$ is yellow, which does not satisfy the fourth requirement. If the color of $(i,j)$ is red, orange, yellow, or green, then the weight $w_{i,j}$ of this cell is $1,2,3,4$ respectively. Among all simple colorings, compute the maximum value of $\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j} w_{i,j}$.

The first line contains two positive integers $n,m$, representing the number of rows and columns of the matrix. Then there are $n$ lines, each containing $m$ integers. The $j$-th integer in the $i$-th line represents $a_{i,j}$.

Output one line containing one integer, representing the answer.

**[Sample Explanation #1]**  The coloring scheme is as shown in the figure above. **[Constraints]** |Test point ID|$n,m\le$|Special property| |:-:|:-:|:-:| |$1\sim 3$|$4$|| |$4\sim 6$|$10$|| |$7\sim 11$|$500$|| |$12$|$2000$|$a_{i,j}\ge 0$| |$13\sim 14$ |$1400$|$\vert a_{i,j}\vert \le 250$| |$15\sim 20$|$2000$|| For all testdata, it is guaranteed that $1\le n,m\le 2000$ and $|a_{i,j}|\le 10^9$。 Translated by ChatGPT 5