Minimum Path Cost

You are given a grid with m rows and n columns containing non-negative integers. Starting from the top-left cell, your goal is to reach the bottom-right cell by moving only right or down at each step.

The cost of a path is the sum of all numbers on that path. Formally, if you denote the cost to reach cell (i, j) by \(dp[i][j]\), then the recurrence relation is given by:

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

You need to compute and output the minimum cost required to traverse from the top-left to the bottom-right cell.

inputFormat

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

outputFormat

Output a single integer representing the minimum path cost from the top-left cell to the bottom-right cell.

3 3
1 3 1
1 5 1
4 2 1

7