Problem L
Grid Gobble

Grid Gobble is a game played on a retangular grid with $r$ rows and $c$ columns, where each cell in the grid contains a positive integer. A game consists of $r$ moves.

For your first move, you pick a number $n$ from the bottom row. Your score for that move is $n$.

For each subsequent move, you pick from the next row up. You can pick the number directly above your previous pick, in which case your score increases by that number. Alternatively, you can pick the number diagonally above to either the left or the right, in which case your score decreases by that number. (If your previous move was in the first column, "diagonally above to the left" wraps around to the last column; if your previous move was in the last column, "diagonally above to the right" wraps around to the first column.) When you eventually pick a number from the top row the game is over.

For example, consider this grid

The best sequence of moves is to choose 8 from the bottom row for $+8$, 1 from the middle row for $-1$, and 9 from the top row for $+9$, as illustrated with the boldface numerals. These moves yield a score of 16.

Input

The first line contains the number of rows $r$ and columns $c$, where $2 \le r \le 1000$ and $3 \le c \le 1000$.

The remaining $r$ lines of the input each contain $c$ integers that lie between 1 and 1000000, inclusive. The first line corresponds to the topmost row of the board and so on down to the last line, which corresponds to the bottommost row of the board.

Output

Print the maximum score possible from the board.

3 3
4 9 4
3 1 2
3 5 8

16

3 4
9 2 1 3
3 7 6 1
1 2 3 9

15

5 4
1 1 1 10000
1 1 1 1
10000 1 1 1
1 1 1 1
1 1 1 10000

29998