There are N stacks of boxes placed and each stack has R boxes. Each box has certain number of gold coins that are passed as the input. Mr.X can totally pick R boxes one in each row. Mr.X can pick a box from any one of the stacks starting from the top row. But the next time he picks a box in the row below, he can only pick a box from the same stack or any one of the adjacent stacks (The left most and right most stack will only have one adjacent stack). The program must print the maximum number of coins Mr.X can pick.
Boundary Condition(s):
2 <= N, R <= 50
1 <= Each integer value <= 10^5
Input Format:
The first line contains N and R separated by a space.
The next N lines, each contains R integers separated by a space.
Output Format:
The first line contains the maximum number of coins Mr.X can pick.
Example Input/Output 1:
Input:
3 4
400 300 100 50
50 100 20 20
300 20 500 10
Output:
1020
Explanation:
There are three stacks. For each stack, the coins from bottom to top are provided. So the boxes with coins is represented as a matrix as below.
50 20 10
100 20 500
300 100 20
400 50 300
The maximum coins 1020 can be collected by collecting
20 from row1, 500 from row2, 100 from row3 and 400 from row4.
Example Input/Output 2:
Input:
3 4
400 300 100 50
50 100 20 20
600 20 500 10
Output:
1220
