Minimum Path Sum in a Grid

You are given an m x n grid filled with non-negative integers. Your task is to find a path from the top-left corner to the bottom-right corner of the grid such that the sum of all numbers along the path is minimized. You can only move either down or right at any point in time.

If the grid is empty or has no columns, the answer is defined to be 0.

Note: The optimal substructure of this problem can be expressed by the recurrence:

$$dp[i][j] = grid[i][j] + \min(dp[i-1][j], \; dp[i][j-1]) $$

with initial conditions on the first row and first column.

inputFormat

The input is read from standard input. The first line contains two integers m and n separated by a space, representing the number of rows and columns in the grid respectively. The next m lines each contain n integers separated by spaces, representing the values in the grid.

If m or n is 0, the grid is considered empty and the output should be 0.

outputFormat

Output the minimum path sum from the top-left corner to the bottom-right corner. The result should be printed to standard output.

## sample

3 3
1 3 1
1 5 1
4 2 1

7