Minimum Path Sum in a Grid

Given an m × n grid filled with non-negative integers, find a path from the top-left corner to the bottom-right corner which minimizes the sum of all numbers along its path. You may only move either right or down at any step. The problem can be modeled using dynamic programming with the recurrence:

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

with the base cases defined as:

• $$dp[0][0] = grid[0][0]$$
• For the first row: $$dp[0][j] = dp[0][j-1] + grid[0][j]$$ (for \(j \ge 1\))
• For the first column: $$dp[i][0] = dp[i-1][0] + grid[i][0]$$ (for \(i \ge 1\))

If the grid is empty, the output should be 0.

inputFormat

The input is given from stdin in the following format:

m n
row1_element1 row1_element2 ... row1_elementn
row2_element1 row2_element2 ... row2_elementn
... (m rows in total)

Here, m and n are the number of rows and columns respectively. If the grid is empty, m and n will be 0.

outputFormat

Output a single integer to stdout which is the minimum sum of a path from the top-left corner to the bottom-right corner. If the grid is empty, output 0.

## sample

3 3
1 3 1
1 5 1
4 2 1

7