Minimum Path Sum in a Grid

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 such that the sum of all numbers along the path is minimized. You are only allowed to move either right or down at any point in time. The state transition formula for dynamic programming is given by:

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

where (dp[i][j]) represents the minimum path sum to reach the cell at row (i) and column (j). The answer is the value of (dp[m-1][n-1]).

The input is provided via standard input where the first line contains two integers ((m) and (n)) representing the number of rows and columns, followed by (m) lines of (n) space-separated integers representing the grid. Print the minimum sum path as output to standard output.

inputFormat

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

outputFormat

Output a single integer, which is the minimum path sum from the top-left corner to the bottom-right corner of the grid.## sample

3 3
1 3 1
1 5 1
4 2 1

7