Problem Background

The problem first defines a matrix ring as follows: given a matrix \( A \) initially all white, select a submatrix \( A_1 \) within it and mark it black, then select another submatrix \( A_2 \) within \( A_1 \) and mark it white, forming a matrix ring. Note that a matrix ring must have selected parts on all four sides (top, bottom, left, right), and the entire matrix ring is not a rectangular matrix.

Assuming + represents black and - represents white, the following is a matrix ring:

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

The following is not a matrix ring:

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

Thus, a matrix ring will have four edges (top, bottom, left, right), and the number of black parts in each direction determines the thickness in that direction. For example, in the first valid diagram, the thickness on the top and right is \( 1 \), and on the left and bottom is \( 2 \).

Note that a complete matrix is not a matrix ring.

Next is the actual problem background:

After obtaining the clue "Tsumugi found some small insects,"最原 immediately took action. First, he used the device resembling a flamethrower (originally belonging to入间) to inhale some air. Then, he planned to use机望's mechanical eye for inspection.

Problem Description

机望's mechanical eye can scan an \( n \times m \) area, where the anomaly value at the \( i \)-th row and \( j \)-th column is \( a_{i,j} \).

Due to severe external forces,机望 can only lock onto a matrix ring for inspection. He seeks your help to find a matrix ring such that the sum of the anomaly values within this matrix ring is maximized, with the top and bottom thicknesses being \( 1 \) and the top row being the first row of the entire area, and the bottom row being the last row of the entire area. As for the left and right thicknesses,机望 does not impose additional restrictions.

Input Format

The first line contains two integers \( n \) and \( m \) representing the size of the area.
The next \( n \) lines each contain \( m \) integers \( a_{i,j} \) representing the anomaly values at each position.

Output Format

Output a single integer representing the answer.
If no valid matrix ring can be selected, output \(-1\).

Sample Input and Output

Sample Input #1

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

Sample Output #1

8

Sample Input #2

1 2
11 45

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

176

Notes/Hints

Sample Explanation

For Sample 1:

A matrix ring can be selected in the following form (but both solutions are the same since the sum of the first column is \( 0 \)):

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

Where + represents selected and - represents unselected.

For Sample 3, provided by @cmll02, thanks for his contribution.

Data Size and Constraints

This problem uses subtask testing.

• 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 additional constraints.

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

见题面 Input 部分

见题面 Output 部分