Minimum Path Sum

Given a grid of size \(N \times M\), where each cell contains a non-negative integer cost, your task is to find the minimum path sum from the top-left corner to the bottom-right corner. At each step, you can only move either right or down.

The problem can be formulated as follows:

Let \( grid[i][j] \) be the cost at cell \( (i, j) \). Define \( dp[i][j] \) as the minimum path sum to reach cell \( (i, j) \). Then the recurrence relation is

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

inputFormat

The first line of input contains two integers \(N\) and \(M\) representing the number of rows and columns in the grid. The following \(N\) lines each contain \(M\) space-separated integers representing the grid.

outputFormat

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

3 3
1 3 1
1 5 1
4 2 1

7