Minimum Path Sum

You are given an (m \times n) grid filled with non-negative integers. Your task is to find a path from the top-left corner to the bottom-right corner which minimizes the sum of the numbers along its path.

You are only allowed to move either downward or rightward at any point. The dynamic programming recurrence for this problem is given by:

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

where the boundaries are handled appropriately by initializing the first row and column.

inputFormat

The input is read from standard input (stdin).

The first line contains two space-separated integers, R and C, representing the number of rows and columns of the grid, respectively.

Each of the next R lines contains C space-separated integers representing the grid.

outputFormat

Output a single integer to standard output (stdout), which is the minimum path sum from the top-left to the bottom-right of the grid.## sample

3 3
1 3 1
1 5 1
4 2 1

7