Minimum Path Sum

Given an m x n grid filled with non-negative integers, find a path from the top left to the bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

The problem can be formulated as follows: Let \(dp(i,j)\) be the minimum path sum to reach cell \((i,j)\). The recurrence relation is given by:

[ 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], \quad dp(i,0) = grid[i][0] + dp(i-1,0), \quad dp(0,j) = grid[0][j] + dp(0,j-1). ]

Compute the minimum sum path from the start at cell (1,1) to the end at cell (m,n), where movement is only permitted to the right or downward.

inputFormat

The first line of input contains two integers m and n separated by a space, representing the number of rows and columns in the grid, respectively.

This is followed by m lines, each containing n space-separated integers, representing the grid's rows.

outputFormat

Output a single integer: the minimum path sum from the top-left corner to the bottom-right corner of the grid.

## sample

3 3
1 3 1
1 5 1
4 2 1

7