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