Matrix Coloring Optimization

You are given an (n\times m) matrix where the cell in the (i)-th row and (j)-th column (denoted by ((i,j))) contains an integer (a_{i,j}).

Define the following relative positions between two cells ((a,b)) and ((c,d)):

• \((a,b)\) is said to be **below** \((c,d)\) if and only if \(b=d\) and \(a>c\) (i.e. in the same column, the row index is larger).
• \((a,b)\) is **above** \((c,d)\) if and only if \((c,d)\) is below \((a,b)\).
• \((a,b)\) is **right of** \((c,d)\) if and only if \(a=c\) and \(b>d\) (i.e. in the same row, the column index is larger).
• \((a,b)\) is **left of** \((c,d)\) if and only if \((c,d)\) is right of \((a,b)\).

For example, in the diagram shown, cell \(A(2,2)\) has cells \(D(3,2)\) and \(E(4,2)\) below it, and cells \(B(2,3)\) and \(C(2,4)\) to its right.

We wish to color each cell with one of four colors: red, orange, yellow, or green. There are many possible colorings, but a coloring is defined to be a **simple scheme** if it satisfies the following constraints for every cell:

For a red cell:

• All cells above it (in the same column) must be red.
• All cells to its left (in the same row) must be red or yellow.
• All cells to its right (in the same row) must be red or orange.

For an orange cell:

• All cells to its right (in the same row) must be orange.
• All cells above it (in the same column) must be red or orange.
• All cells below it (in the same column) must be orange or green.

For a green cell:

• All cells below it (in the same column) must be green.
• All cells to its right (in the same row) must be green or orange.
• All cells to its left (in the same row) must be green or yellow.

For a yellow cell:

• All cells to its left (in the same row) must be yellow.
• All cells below it (in the same column) must be yellow or green.
• All cells above it (in the same column) must be yellow or red.

A couple of examples are given in the picture. Note that if a particular color does not appear in the scheme, the corresponding restrictions are ignored.

Each cell \((i,j)\) is assigned a weight \(w_{i,j}\) depending on its color as follows:
\[ w_{i,j} = \begin{cases} 1, & \text{if red},\\ 2, & \text{if orange},\\ 3, & \text{if yellow},\\ 4, & \text{if green}. \end{cases} \]

Your task is to compute the maximum value of

\[ S = \sum_{i=1}^{n} \sum_{j=1}^{m} a_{i,j} \cdot w_{i,j} \]

among all simple schemes.

A key observation is that every simple scheme has the following structure: there exist two integers \(X\) (with \(1 \le X \le n+1\)) and \(Y\) (with \(1 \le Y \le m+1\)) such that:

• For all cells with \(i < X\) and \(j < Y\), the color is red.
• For all cells with \(i < X\) and \(j \ge Y\), the color is orange.
• For all cells with \(i \ge X\) and \(j < Y\), the color is yellow.
• For all cells with \(i \ge X\) and \(j \ge Y\), the color is green.

Using this observation, the value \(S\) can be rewritten as:

\[ S = 1\cdot \Big(\sum_{i=1}^{X-1}\sum_{j=1}^{Y-1} a_{i,j} \Big) + 2\cdot \Big(\sum_{i=1}^{X-1}\sum_{j=Y}^{m} a_{i,j} \Big) + 3\cdot \Big(\sum_{i=X}^{n}\sum_{j=1}^{Y-1} a_{i,j} \Big) + 4\cdot \Big(\sum_{i=X}^{n}\sum_{j=Y}^{m} a_{i,j} \Big). \]
Your goal is to choose \(X\) and \(Y\) optimally to maximize \(S\).

inputFormat

The first line contains two integers (n) and (m) (the number of rows and columns).

Each of the next (n) lines contains (m) integers, where the (j)-th integer in the (i)-th line is (a_{i,j}).

outputFormat

Output a single integer representing the maximum value of (\sum_{i=1}^{n}\sum_{j=1}^{m} a_{i,j}w_{i,j}) over all simple schemes.

sample

3 3
1 2 3
-1 0 4
2 -3 1

36