Covering the grid

Time limit1sMemory limit256 MB

Summary

Place corner-touching rectangles chaining from the top-left cell to the bottom-right cell to maximize the sum of covered cell values.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

Myungwoo has an $R$ by $C$ grid with one integer written in each cell. He also has rectangular boards of many sizes, and he covers the grid with several of them under these rules.

Every board lies inside the grid and parallel to it. Covering only part of a cell is not allowed.
The first board contains the cell in row 1, column 1.
From the second board on, each board touches the bottom right corner point of the board placed just before it, and the edges of the two boards must not touch. So if the previous board ends at the cell in row $r$ , column $c$ , the next board starts at the cell in row $r+1$ , column $c+1$ .
The last board contains the cell in row $R$ , column $C$ .

The picture below shows one covering of an 8 by 8 grid that follows the rules.

A covering of an 8 by 8 grid that follows the rules

The score is the sum of the integers written in the covered cells. A cell that no board covers adds nothing. Given the grid, find the largest score Myungwoo can get.

Input

The first line has two natural numbers $R$ and $C$ .

Each of the next $R$ lines has the $C$ values of one row, separated by spaces. The absolute value of every entry is at most $10^4$ .

The bounds are $1 \le R, C \le 300$ .

Output

Print, on one line, the largest score obtainable under the rules.

Examples2

Example 1
Input
```
2 2
1 -1
-1 1
```
Expected output
```
2
```

Example 2

Input

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

Expected output