Minimum Cost Grid Path

You are given a grid with \(N\) rows and \(M\) columns. Each cell in the grid contains either a non-negative integer cost or a trap represented by the character X.

Your task is to compute the minimum cost required to travel from the top-left cell (cell \((1,1)\)) to the bottom-right cell (cell \((N,M)\)) by only moving either to the right or down. If a cell is a trap (i.e. contains X), you cannot step on that cell.

If it is impossible to reach the bottom-right corner from the top-left corner, output \(-1\).

Note: The cost of a path is defined as the sum of the costs of all visited cells (including the starting and ending cells). The grid indices are 1-indexed in the problem statement though you may use 0-indexed arrays in your solution.

inputFormat

The input is given in stdin and consists of multiple datasets. Each dataset is described as follows:

• A line containing two integers \(N\) and \(M\) ( \(1 \leq N, M \leq 1000\) ), the number of rows and columns of the grid.
• Then follow \(N\) lines, each containing \(M\) space-separated tokens. Each token is either an integer (representing the cost) or the character X (representing a trap).

The input terminates with a line containing "0 0" which should not be processed.

outputFormat

For each dataset, output a single line in stdout containing the minimum cost required to reach the bottom-right cell. If the destination is unreachable, output \(-1\).

## sample

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

21

</p>