Minimum Cost Path in a Grid

You are given a grid of size ( M \times N ) where each cell contains a non-negative cost. Your task is to find the minimum cost path from the top-left cell (0,0) to the bottom-right cell (M-1, N-1). You can only move either to the right or down at each step. The dynamic programming recurrence for this problem is given by: [ \text{dp}[i][j] = \min(\text{dp}[i-1][j],, \text{dp}[i][j-1]) + \text{grid}[i][j] ] with the base conditions being ( \text{dp}[0][0] = \text{grid}[0][0] ), the first row ( \text{dp}[0][j] = \text{dp}[0][j-1] + \text{grid}[0][j] ), and the first column ( \text{dp}[i][0] = \text{dp}[i-1][0] + \text{grid}[i][0] ).

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains two space-separated integers ( M ) and ( N ), representing the number of rows and columns of the grid respectively. The next ( M ) lines each contain ( N ) space-separated integers, representing the cost of each cell in the grid.

outputFormat

Output a single integer to standard output (stdout), which is the minimum cost to reach the bottom-right cell of the grid from the top-left cell under the allowed moves.## sample

3 3
1 3 1
1 5 1
4 2 1

7