You are playing a matrix-based game with the following setup and rules:
- You are given a matrix with rows and columns. Each cell contains some points. When a player passes a cell their score increases by the number written in that cell and the number in the cell becomes . (If the cell number is positive their score increases, otherwise it decreases.)
- The player starts from any cell in the first row and can move left, right or down.
- The game is over when the player reaches the last row and stops moving.
Print the maximum score that the player can get.
Input Format
The first line contains and . The next lines contain numbers each, number in line denotes the number that is written on cell .
Constraints
Subtasks
- for tests .
- for tests .
Output Format
Print the maximum score that the player can get.
Sample Input 0
4 5
1 2 3 -1 -2
-5 -8 -1 2 -150
1 2 3 -250 100
1 1 1 1 20
Sample Output 0
37
Explanation 0
Refer the image given in statement, the path followed is summing upto .
Note that, is traversed times, but the second time it only contributes to the sum.