Minimum Path Sum

You are given a grid of non-negative integers. Your task is to compute the minimum sum of numbers along a path from the top-left corner to the bottom-right corner. You can only move either right or down at any step.

The problem can be formalized as follows: Given a grid \( grid \) of dimensions \( n \times m \), find the minimum path sum where \[ dp[i][j] = grid[i][j] + \min(dp[i-1][j],\ dp[i][j-1]) \] with suitable base cases.

inputFormat

The input is provided via standard input (stdin) and has the following format:

• The first line contains two space-separated integers \( n \) and \( m \) — the number of rows and columns of the grid.
• The following \( n \) lines each contain \( m \) space-separated integers representing the grid.

outputFormat

Output a single integer to standard output (stdout) — 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