Background

The problem first defines a matrix ring as follows: given a matrix $A$, which is initially all white, select a submatrix $A_1$ in it and paint it black, then select a submatrix $A_2$ inside $A_1$ and paint it white, and a matrix ring is formed. Note that a matrix ring must have selected parts on all four sides (top, bottom, left, and right), and the whole matrix ring is not a rectangular matrix.

Assume + is black and - is white. The following is a matrix ring:

---+++++--
---++--+--
---+++++--
---+++++--
----------

The following are not matrix rings:

------- ------
---+++- --+++-
---+-+- --+++-
------- --+++-

Therefore, a matrix ring has four sides: top, bottom, left, and right. For each direction, the number of painted-black layers is the thickness in that direction. For example, in the first valid figure, the thicknesses of the top and right sides are $1$, and the thicknesses of the left and bottom sides are $2$.

Note that a complete matrix is not a matrix ring.

Next is the actual background story:

After Saihara got the clue "Gokuhara found some small bugs", he took action immediately. First, he used Iruma's relic, the thing that looked like a flamethrower, to suck in some air. Then, he planned to use Kibo's mechanical eye to inspect it.

Problem Description

Kibo's mechanical eye can scan an $n \times m$ area. At row $i$ and column $j$, it detects an abnormality value of $a_{i,j}$.

Because Kibo is severely tortured by external forces, he can only lock onto one matrix ring to inspect. Kibo wants to ask you for help: he wants you to lock onto a matrix ring such that the sum of abnormality values of all positions in the matrix ring is maximized, the thicknesses of the top and bottom sides are $1$, and the top row is the first row of the whole area, while the bottom row is the last row of the whole area. As for the left and right thicknesses, Kibo has no further constraints.

Input Format

The first line contains two integers $n, m$, representing the size of the whole area.
Then $n$ lines follow, each containing $m$ integers $a_{i,j}$, representing the abnormality value at each position.

Output Format

Output one integer in one line, representing the answer.
If it is impossible to choose a matrix ring that satisfies the requirements, output $-1$.

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

8

1 2
11 45

-1

7 7
10 10 10 -100 11   11 11
10 10 10 -100 11 -100 11
10 10 10 -100 11 -100 11
10 10 10 -100 11 -100 11
10 10 10 -100 11 -100 11
10 10 10 -100 11 -100 11
10 10 10 -100 11   11 11

176

Hint

Sample Explanation

Explanation for Sample 1:

You can choose a matrix ring of the following form (but in fact the two solutions are the same, because the sum of all numbers in the first column is $0$):

++++  -+++
++-+  -+-+
++-+  -+-+
++++  -+++

Here, + means selected, and - means not selected.

For Sample 3, the provider is

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (5 pts): $n \le 2$ or $m \le 2$.
• Subtask 2 (5 pts): $a_{i,j} > 0$.
• Subtask 3 (40 pts): $m \le 1000$.
• Subtask 4 (50 pts): No special constraints.

For $100\%$ of the testdata, $1 \le n \le 10$, $1 \le m \le 10^5$, $|a_{i,j}| \le 100$.

Translated by ChatGPT 5