Super Plumber

You are to write a program for a video game in which Super Plumber (SP) navigates an obstacle course, collecting prizes on his way to rescuing the Princess (TP).

The obstacle course is an $m$ by $n$ grid. SP starts at the bottom-left corner and makes his way to the Princess in the bottom-right corner. Some cells are occupied by obstacles that SP cannot pass through; other cells hold gold coins valued between $1.00 and $9.00.

The game is a traditional side-scroller, so SP may move only right, up, or down, one cell at a time, always into an adjacent cell that has no obstacle. He can never occupy a cell he has already occupied: once he moves up he cannot move down until he next moves right, and once he moves down he cannot move up until he next moves right. SP collects the coin at every cell he visits. Find the maximum total value of coins SP can collect on a route from the bottom-left corner to the bottom-right corner.

The input contains several test cases. The first line of each test case has two integers $m$ and $n$ ($2 \le m, n \le 100$). The grid follows as $m$ lines of $n$ characters each:

• * marks an obstacle,
• a digit 1-9 marks a coin of that value,
• . marks an empty cell.

It is always possible for SP to reach the Princess. A line containing 0 0 follows the last test case and must not be processed.

For each test case, print one line containing the maximum total value of coins SP can collect on a valid route from the bottom-left corner to the bottom-right corner. Because every coin is a whole number of dollars, the answer is an integer; print it with no dollar sign and no decimal part.