Minimum Path Sum

You are given one or more datasets representing grids. For each grid, you must find the minimum path sum from the top-left corner to the bottom-right corner. You can only move either right or down at any step. The path sum is defined as the sum of the values in the cells visited.

The recurrence relation is given by:

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

Each grid is provided with its dimensions m and n followed by m lines each containing n integers. The input terminates with a line containing "0 0".

Your task is to compute and output the minimum path sum for each grid dataset.

inputFormat

The input is read from standard input (stdin). It contains multiple datasets. Each dataset begins with two integers m and n (the number of rows and columns, respectively). Following this, there are m lines each with n integers representing the grid. The end of input is signaled by a line containing "0 0".

outputFormat

For each dataset, output a single line containing the minimum path sum from the top-left to the bottom-right of the grid.## sample

3 3
1 3 1
1 5 1
4 2 1
2 2
1 2
1 1
0 0

7
3