Minimum Path Sum

You are given a grid of non-negative integers with dimensions \(m \times n\). Your task is to find the minimum path sum from the top-left corner to the bottom-right corner. You are only allowed to move either down or right at any point in time.

The problem can be solved using dynamic programming. Let \(dp[i][j]\) represent the minimum path sum to reach cell \((i,j)\). The recurrence relation is given by:

[ \begin{aligned} dp[i][j] &= grid[i][j] + \min(dp[i-1][j], dp[i][j-1]) \quad \text{for } i,j > 0, \ dp[i][0] &= grid[i][0] + dp[i-1][0] \quad \text{for } i > 0, \ dp[0][j] &= grid[0][j] + dp[0][j-1] \quad \text{for } j > 0, \ dp[0][0] &= grid[0][0]. \end{aligned} ]

Your program should read the grid from standard input and output the minimum path sum to standard output.

inputFormat

The first line of input contains two integers \(m\) and \(n\) (the number of rows and columns of the grid). Each of the next \(m\) lines contains \(n\) space-separated non-negative integers representing the grid.

outputFormat

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

3 3
1 3 1
1 5 1
4 2 1

7