409507: GYM103604 B Dungeon

Danny is an avid fan of Dungeon Crawlers and spends his time either playing them, or talking about them. Recently, he started wondering if it's possible for a computer to play one of his games, and he's been asking you to try it out for him.

The game is split into L levels, with N x M cells on every level. Every cell can have one of the following values:

• 0 - representing an empty cell;
• -1 - representing the exit to the next level;
• -9 - representing an obstacle you cannot pass through;
• K ($$$1 \leq K \leq 10^9$$$) - an integer representing the power level of an enemy.

In order to beat an enemy, your power needs to be greater than or equal to its power. Upon defeating it, you absorb its energy and your own power increases by a value equal to the power of the defeated enemy.

Given that you start with a power of 1 in the top left corner of the first level of the dungeon, what's the maximum power you can achieve? A path to the last level is always guaranteed.

The first line of input contains three integers: L N M, representing the number of levels, the number of rows and the number of columns ($$$1 \leq L * N * M \leq 10^6$$$). Then, there are L groups of N rows and M columns, describing the layout of the dungeon level.

On a single line, print an integer $$$P$$$ representing the maximum power you can get at the end of the dungeon.

1 5 5
0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
0 0 0 0 1
5 0 0 0 0

4

2 5 5
0 0 -9 0 1
0 0 -9 -9 -9
0 0 1 0 0
0 0 -1 0 1
4 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 3 0 0
0 0 0 0 1
5 0 0 0 0

13