You are being chased! However, you also have a strong attraction towards shiny thing 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 you 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 file DATA3.txt will contain 5 cases, each an 8x8 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 file OUT3.txt 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.

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

12