Minimum Path Sum

Given a 2D grid of non-negative integers, find the minimum path sum from the top-left corner to the bottom-right corner. You are only allowed to move either to the right or down at any point in time.

The path sum is defined as the sum of all the numbers along the chosen path.

For example, for the grid ( \begin{bmatrix}1 & 3 & 1\ 1 & 5 & 1\ 4 & 2 & 1\end{bmatrix} ), one of the optimal paths is 1→3→1→1→1 which gives a minimum path sum of 7.

inputFormat

The first line contains two integers, ( m ) and ( n ), representing the number of rows and columns respectively. This is followed by ( m ) lines; each line contains ( n ) space-separated non-negative integers representing the grid.

outputFormat

Output a single integer representing the minimum path sum from the top-left corner to the bottom-right corner.## sample

3 3
1 3 1
1 5 1
4 2 1

7