Minimum Falling Path Sum

matrix is a grid of numbers. A falling path starts at any cell of the first row and moves down one row at a time, to the cell directly below or diagonally below left or right. Return the smallest sum of a falling path. An empty matrix gives 0.

For [[2, 1, 3], [6, 5, 4], [7, 8, 9]] the answer is 13 (1 + 5 + 7).

Examples

Example 1

Input:

min_falling_path_sum([[2, 1, 3], [6, 5, 4], [7, 8, 9]])

Output:

13

Example 2

Input:

min_falling_path_sum([[-19, 57], [-40, -5]])

Output:

-59

Constraints

• 0 <= rows, cols <= 500
• -100 <= value <= 100