Grid Gobble is a game played on a rectangular grid with r rows and cc 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
4 9 4
3 1 2
3 5 8
The best sequence of moves is to choose 8 from the bottom row for +8+8, 1 from the middle row for −1−1, and 9 from the top row for +9+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 cc, where 2≤≤10002≤r≤1000 and 3≤c≤10003≤c≤1000.
The remaining r lines of the input each contain cc 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.
Sample Input 1 Sample Output 1
3 3
4 9 4
3 1 2
3 5 8
16

Sample Input 2 Sample Output 2
3 4
9 2 1 3
3 7 6 1
1 2 3 9
15

Sample Input 3 Sample Output 3
5 4
1 1 1 10000
1 1 1 1
10000 1 1 1
1 1 1 1
1 1 1 10000
29998
Detailed Pseudocode of this is the help that i need.