Minimum Path Cost in a Grid

You are given a 2D grid of 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 the numbers on the path is minimized. You are only allowed to move either right or down at any step.

The problem can be formulated using dynamic programming. Define \(dp[i][j]\) as the minimum cost to reach cell \((i, j)\). The recurrence relation is given by:

[ \begin{aligned} dp[i][j] = \min(dp[i-1][j], ; dp[i][j-1]) + grid[i][j] \end{aligned} ]

with the boundary conditions that \(dp[0][0] = grid[0][0]\), the first row and first column are filled by cumulative sums.

Read the grid from standard input and write the result to standard output.

inputFormat

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

outputFormat

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

3 3
1 3 1
1 5 1
4 2 1

7