Minimum Path Sum

You are given a grid (matrix) of size n x m 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 the path.

You can only move either down or right at any point in time. The problem can be solved using dynamic programming. The recurrence relation used in dynamic programming is given by:

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

where dp[i][j] represents the minimum path sum to reach cell (i, j). Your job is to compute the minimal path sum from the top-left cell to the bottom-right cell.

inputFormat

The input is read from standard input (stdin). The first line contains two integers n and m separated by a space, indicating the number of rows and columns of the grid, respectively. Following this, there are n lines, each containing m space-separated integers representing the grid.

outputFormat

Output a single integer: the minimum path sum from the top-left corner to the bottom-right corner. The output should be written to standard output (stdout).

## sample

3 3
1 3 1
1 5 1
4 2 1

7