Minimum Path Sum

Given a grid of non-negative integers with R rows and C columns, find a path from the top-left cell to the bottom-right cell which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

Note: The grid is given as a matrix with dimensions R x C. The objective is to compute the minimum path sum using dynamic programming techniques.

The problem can be modeled with the recurrence relation:

\(dp[i][j] = grid[i][j] + \min(dp[i-1][j],\, dp[i][j-1])\) with appropriate boundary conditions.

inputFormat

The input is given via standard input (stdin). The first line contains two integers R and C representing the number of rows and columns. Each of the following R lines contains C space-separated integers representing the grid.

For example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Output the minimum path sum from the top-left cell to the bottom-right cell. The answer should be written to standard output (stdout).

For the above example, the output is:

7

## sample

3 3
1 3 1
1 5 1
4 2 1

7