Minimum Elevation Path

You are given an elevation matrix of size H × W. The task is to find the minimum possible sum of elevations along a path from the top-left corner to the bottom-right corner.

You can only move either right or down at any step. The recurrence relation used is given by the formula:

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

where dp[i][j] represents the minimum sum required to reach cell (i, j) in the matrix.

The input may consist of multiple datasets. Each dataset starts with two integers H and W (the number of rows and columns respectively). Then follow H lines each containing W integers representing the elevation matrix. The input is terminated by a line containing "0 0" which should not be processed.

inputFormat

The input consists of one or more test cases. Each test case is formatted as follows:

• The first line contains two integers H and W, where 1 ≤ H, W ≤ 1000.
• The next H lines each contain W integers representing the elevation values of the matrix.

The end of input is indicated by a line with "0 0".

outputFormat

For each test case, output a single line containing the minimum sum of elevations along the path from the top-left to the bottom-right corner.

## sample

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

7
3

</p>