You found a grid with rows and columns, and each cell of the grid has some positive integer value . You are allowed to keep some subset of the cells of the grid as follows:
- First, you must make some number of horizontal or vertical cuts along the grid lines. This cuts the grid into several rectangular regions that form a grid pattern. You must make at least one cut, but it is allowed to make only horizontal or only vertical cuts.
- Next, you colour this new grid with two colours in a checkerboard pattern, where any two adjacent rectangular regions have a different colour.
- Finally, you are allowed to keep all the grid cells that have the same colour.
You want to maximize the total value of all the cells you keep. Calculate this maximum possible sum.
For all test cases, at least one of or is greater than and for all grid cells.
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [30%]
Subtask 4 [25%]
Subtask 5 [25%]
The first line of input contains two space-separated integers: and . The next lines of input contain space-separated integers, describing a row of the grid. The th number on the th of these lines is the value .
Output one number: the maximum possible total value of all cells you keep.
Sample Input 1
1 4 6 2 9 8
Sample Output 1
Explanation for Sample Output 1
By making two vertical cuts, it is possible to keep all values except for the .
Sample Input 2
3 4 9 1 7 8 2 8 1 1 7 3 5 6
Sample Output 2
Explanation for Sample Output 2
Make two horizontal cuts and two vertical cuts as shown below:
You can keep all the values in black cells, giving a total value of .