Minimum Cost Path in Grid

Problem Statement:

You are given a grid ( grid ) of size ( m \times n ) where each cell contains a non-negative integer representing the cost of stepping on that cell. Starting from the top-left corner, you need to find the minimum cost to reach the bottom-right corner. You can only move either right or down at any step.

Formally, if ( grid[i][j] ) denotes the cost of cell ( (i,j) ), you need to find the minimum cost path from ( grid[0][0] ) to ( grid[m-1][n-1] ) such that the cost of the path is minimized. The recurrence relation is given by:

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

with appropriate boundary conditions.

For example, consider the grid:
1 3 1
1 5 1
4 2 1

The minimum cost path is 1 → 3 → 1 → 1 → 1, which results in a total cost of 7.

inputFormat

Input is read from STDIN. The first line contains two integers ( m ) and ( n ), representing the number of rows and columns respectively.

Each of the next ( m ) lines contains ( n ) non-negative integers separated by spaces, denoting the grid.

outputFormat

Output the minimum cost to reach the bottom-right corner from the top-left corner. The result should be printed to STDOUT.## sample

3 3
1 3 1
1 5 1
4 2 1

7