Minimum Path Sum in a Grid

You are given a two-dimensional grid of integers with m rows and n columns. 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. At any cell, you can only move either right or down.

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

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

The answer will be the value of \(dp[m-1][n-1]\), which gives the minimum sum from the start to the finish.

Example:

Input:
3 3
1 3 1
1 5 1
4 2 1
Output:
7

</p>

inputFormat

The first line of input contains two integers m and n separated by a space, representing the number of rows and columns of the grid, respectively. This is followed by m lines, each containing n integers separated by spaces, representing the grid.

For example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Output a single integer, representing the minimum sum from the top-left to the bottom-right cell of the grid using a path that only moves right or down.

## sample

3 3
1 3 1
1 5 1
4 2 1

7