821. Fall Guys

0

Medium

In the final round of a Fall Guys match, you must navigate through a square matrix of size n * n. Starting from any position in the first row, you can move to the block directly in front of you (b[i+1][j]), or to any of the blocks diagonally connected to your current block (b[i+1][j-1] or b[i+1][j+1]), as long as you don't fall out of the matrix. However, you cannot move within the same row (b[i][j-1] or b[i][j+1]) or you will fall. Your objective is to find the falling path that results in the maximum sum of all the blocks you pass through, according to the given rules and matrix.

Input Format

The first line of input consists of two integers N (number of rows) and M (number of columns) of the matrix. The next N lines contain M space-separated integers that describe the matrix.

Output Format

Print the minimum sum of any falling path through the matrix.

Example

Input

3 3 2 1 3 6 5 4 7 8 9

Output

13

Constraints

n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100