Minimum Path Sum

You are given a grid with m rows and n columns filled with non-negative integers. Your task is to find a path from the top-left corner to the bottom-right corner which minimizes the sum of all numbers along its path. You can only move either right or down at any point in time.

The problem can be formulated using the following recurrence relation in LaTeX:

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

with the base cases:

• $$dp[0][0] = grid[0][0]$$
• $$dp[0][j] = grid[0][j] + dp[0][j-1]$$ for $$j > 0$$
• $$dp[i][0] = grid[i][0] + dp[i-1][0]$$ for $$i > 0$$

Compute and output the minimum path sum from the top-left to the bottom-right cell.

inputFormat

The input is given from standard input (stdin) in the following format:

m n
row1_element1 row1_element2 ... row1_elementn
row2_element1 row2_element2 ... row2_elementn
...
rowm_element1 rowm_element2 ... rowm_elementn

Where m and n are the number of rows and columns respectively, and the following m lines each contain n space-separated non-negative integers representing the grid.

outputFormat

Output a single integer to standard output (stdout) representing the minimum path sum from the top-left to the bottom-right corner of the grid.

## sample

3 3
1 3 1
1 5 1
4 2 1

7