Given an m x n grid of non-negative integers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of values along the path. At each step you may move only right or down. Return that minimum sum.
Input
grid: 2D array of non-negative integers
Output
The minimum sum of values along any valid path.
Examples
Example 1
Inputgrid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output21
Explanation: The path 1 -> 2 -> 3 -> 6 -> 9 sums to 21.
Example 2
Inputgrid = [[1, 0], [0, 1]]
Output2
Constraints
1 <= m, n; grid[i][j] >= 0.
Moves are restricted to right and down.