Background

Original problem link: https://oier.team/problems/J3E。

Problem Description

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}$.

Input Format

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 Format

Output one line containing one integer, representing the answer.

3 4
8 -2 -5 7
-4 6 -1 -3
5 1 4 3

87

10 10
-607544439 -979004727 -312554064 -699869702 666983975 -320873934 -942207367 -178682386 275703899 -502153774
410971617 -76369893 -359278237 275932972 -86448038 714539457 -54215653 -250390633 -543539625 929531007
718862112 -158262990 482471050 -836696543 791951750 239968249 -766605973 -759094194 -19007257 907151693
-348361375 170949857 -285590070 402599195 469840858 288238039 410877678 179198841 60474475 813298551
-49654250 -340449178 -818518909 981342312 -472457171 144738808 -78496024 119951006 719889194 589539617
-343916789 -102845130 647967162 178223670 -520096558 -701610878 769986590 -306817394 776077393 891533714
-652884066 743855180 513738054 837511580 -206701878 751808326 -442751338 507912998 -51199158 -548890634
-19583239 -517604006 -564570564 -853892671 738975088 851320757 -595055422 852889648 213674342 -548020267
779798717 -323958612 577597457 -318242425 57184511 189209789 347708858 891010501 322410555 -669564400
623568486 123756685 -925342948 -864544839 -83746874 680094424 335536285 -977426931 -724040964 -337707402

26663074561

Hint

[Sample Explanation #1]

The coloring scheme is as shown in the figure above.

[Constraints]

For all testdata, it is guaranteed that $1\le n,m\le 2000$ and $|a_{i,j}|\le 10^9$。

Translated by ChatGPT 5