Minimum Cost Path

You are given several grids where each grid is a two-dimensional array of non-negative integers. Each cell in the grid represents a cost to enter that cell. Starting from the top-left cell, your goal is to reach the bottom-right cell with the minimum total cost. At any step, you are only allowed to move either right or down.

For each grid, compute the minimum cost path from the top-left corner to the bottom-right corner. Use dynamic programming to solve the problem efficiently.

inputFormat

The input consists of multiple datasets. Each dataset starts with a line containing two integers M and N representing the number of rows and columns, respectively. This line is followed by M lines each containing N integers representing the grid. The input terminates with a line containing "0 0" which should not be processed.

outputFormat

For each dataset, output a single line containing the minimum cost to travel from the top-left to the bottom-right cell.

3 3
1 2 3
4 5 6
7 8 9
0 0

21