DWITE Online Computer Programming Contest, November 2010, Problem 3

You are being chased! However, you also have a strong attraction towards shiny things and notice, while running, that people carelessly left valuables lying around on the floor. So, while trying to escape, you want to pick up the most value possible. You are at the bottom leftmost corner of the field, and you are making your way to the top rightmost corner to escape. The only valid moves are up or to the right; so always getting further from the starting point. There is no backtracking.

The input will contain 5 cases, each an ~8 \times 8~ grid, followed by a separating line of dashes. Periods . are empty space, hashes # are walls, digits are value of loot at that location.

The output will contain 5 lines, each an integer — the maximum sum value of the loot that can be picked up during the escape in the 5 test cases above.

Sample Input

..2.....
..2.....
..2.....
.....9..
...##...
...5#...
........
.3......
--------

Sample Output

12

Problem Resource: DWITE