Minimum Path Sum

You are given a grid of non-negative integers with r rows and c columns. Your task is to find the minimum sum path from the top-left corner to the bottom-right corner of the grid. You can only move either down or right at any given step.

The problem can be defined with the following recurrence relation:

$$dp(i,j) = grid_{ij} + \min(dp(i-1,j),\,dp(i,j-1))$$

where dp(i,j) represents the minimum sum to reach cell (i,j) from the top-left corner of the grid.

Print the minimum sum obtained for the given grid.

inputFormat

The first line contains two integers r and c, representing the number of rows and columns in the grid respectively. This is followed by r lines, each containing c space-separated non-negative integers representing a row in the grid.

outputFormat

Output a single integer, which is the minimum sum from the top-left corner to the bottom-right corner of the grid by only moving right or down.## sample

3 3
1 3 1
1 5 1
4 2 1

7