Minimum Path Sum

You are given a 2D grid of 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 all numbers along its path. You can only move either down or right at any point in time.

The problem can be formulated as follows:

Find the minimum value of \(dp[i][j]\) where \[ \begin{aligned} dp[i][j] &= \min(dp[i-1][j],\;dp[i][j-1]) + grid[i][j],\\ \text{with}\quad dp[0][0] &= grid[0][0]. \end{aligned} \]

The solution should read the grid from standard input, and output the minimum path sum to standard output.

inputFormat

The input begins with two integers \(R\) and \(C\), representing the number of rows and columns in the grid. This is followed by \(R\) lines, each containing \(C\) space-separated integers representing the grid's cells.

Example Input:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Output a single integer representing the minimum path sum from the top-left corner to the bottom-right corner.

Example Output:

7

## sample

3 3
1 3 1
1 5 1
4 2 1

7