428. Fall Guys

0

Medium

In the final round of a Fall Guys match, you must navigate a square matrix of integers. 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 diagonally connected blocks (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]). Your objective is to find the falling path that yields the maximum sum of all the blocks you pass through, according to the given rules and matrix.

Input Format

The first line of input contains 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

1 <= n <= 100

-100 <= matrix[i][j] <= 100

Loading...

View Submissions

Console