Given a matrix of N * M. Find the maximum path sum in matrix. The maximum path is sum of all elements from first row to last row where you are allowed to move only down or diagonally to left or right. You can start from any element in first row.

Sample Input1

4

6

10 10 2 0 20 4 1 0 0 30 2 5 0 10 4 0 2 0 1 0 2 20 0 4

Sample Output1

74

Explanation

The first 2 values are the dimension of the matrix. Then the values are given. The maximum sum path is 20-30-4-20