Gybing

The America's Cup 2017 is being contested between Oracle Team USA and Emirates Team New Zealand. It involves sailing ridiculously fast boats up and down between two sets of markers, and seeing which boat is the fastest. To move along, the boats zig-zag up and down the length of the course, catching the wind. Technology plays an important part in the America's Cup, with a lot of advanced materials science and engineering. You have been brought in to consult as a programmer, and find the fastest path down a single length of the course.

The course is described by long grid, $W$ metres wide ($3 \leq W \leq 100$) by $L$ metres long ($1 \leq L \leq 250,000$). Each square metre of the grid has a value $V_{i,j}$ which represents the strength of the wind at that point ($1 \leq i \leq W$, $1 \leq j \leq L$, $0 \leq V_{i,j} \leq 100$). Your boat can start at any point in the first row, and can finish at any point in the final ($L$th) row. Your boat can be travelling either to the left or to the right, and you can choose which direction you face to begin with. Your boat always travels at $45°$ to the wind. For the purposes of simplicity, your boat always occupies exactly one grid cell. The path will hence look like a zig-zag down through the grid (see the sample explanation).

When a boat turns around (from left to right or vice versa) while travelling downwind, it is called a gybe. The boom swings across the centre of the boat, and when the wind catches the sail from the opposite side it can be rather violent. This makes gybing a relatively dangerous manouver, and it is even more difficult in higher winds. We call a point on the zig-zag path where the direction changes an apex.

The score of a path is the sum of the values of the non-apex grid cells it uses, minus the squares of the values of any apex grid cells it uses. That is, when the boat is travelling in a straight line, it's score increases by the value of the grid cell it's on. When it's turning around, it's score decreases by the square of the grid cell it's on.

The path with the highest score is the fastest path.

Input

The first line of input will contain a two integers $W$, $L$, the width and length of the course respectively.

Following that will be $L$ lines, each containing $W$ space separated integers, representing the strength of the wind at each of the grid cells. The $i$th integer on the $j$th line is $V_{i,j}$

Output

Output should contain a single integer - the highest score attainable.

Subtasks

• Subtask 1 (20%): $W = 3$, $N \leq 10$
• Subtask 2 (30%): $W = 3$, $N \leq 1,000$
• Subtask 3 (50%): No further restrictions.

Sample Explanation

The grid described by the sample is shown below, and the optimal path is indicated by brackets around grid cells. Square brackets ([]) indicate apex cells and round brackets (()) indicate non-apex cells. The total is calculated as $9 + 2 - 0^2 + 6 - 2^2 + 3 - 0^2 + 5 - 1^2 + 3 = 23$, where the items added are given in sequence of their row.

(9) 1  1
 5 (2) 3
 1  2 [0]
10 (6) 5
[2] 9  9
 8 (3) 1
 6  4 [0]
10 (5) 5
[1] 5  5
 3 (3) 3