Dungeon Crawlers

Danny is a huge fan of Dungeon Crawlers. Recently, he wondered if a computer could play the game – and he wants you to help him try.

The dungeon contains (L) levels. Each level is a grid of (N \times M) cells. Each cell may contain one of the following:

• 0 represents an empty cell.
• -1 represents an exit to the next level. When you use an exit (which exists in every level except the last), you are teleported to the next level with your initial position set exactly at that exit cell. Note that you cannot step on an exit cell without being teleported.
• -9 denotes an impassable obstacle.
• A positive integer \(x\) (with \(1 \le x \le 10^9\)) represents an enemy whose power is \(x\). To defeat an enemy, your current power must be at least \(x\). After defeating the enemy, your power increases by \(x\). You must defeat an enemy to move onto its cell.

Initially, your power is \(1\). You start at the top‐left cell of the first level (cell \((1,1)\), using 1-indexing), and your goal is to finish in the last level at any cell. On levels that are not the last one, you must exit the level by stepping on the unique exit cell. However, note that once you step on an exit cell, you are forced to teleport immediately – you cannot postpone teleportation even if there are still enemies you could defeat if you had stayed longer.

Determine the maximum power you can have when you finish the game (i.e. after traversing all \(L\) levels). It is guaranteed that there is always a path from the starting cell on level 1 to some cell on the last level.

The tricky part is that in each level you may have a choice: racing to the exit early with a lower power, or postponing the exit (by avoiding the exit cell which acts like a wall until you’re done exploring) in order to defeat more enemies and boost your power. Note that you can only defeat an enemy if it is reachable without stepping on an exit cell (since stepping on the exit forces teleportation).

inputFormat

The first line contains three integers (L), (N), and (M), where (1 \le L \le 10) and (N, M) are the dimensions of each level.

Then, for each level, there are (N) lines; each line contains (M) space‐separated tokens. In each level, -9 represents an impassable obstacle, 0 represents an empty cell, any positive integer represents an enemy’s power, and (for levels 1 to (L-1)) exactly one cell will contain -1 denoting the exit. (The last level does not have an exit cell.)
It is guaranteed that there is a valid way to reach the last level from the starting position.

outputFormat

Output a single integer – the maximum power you can have when you finish the game.

sample

1 3 3
0 1 0
0 2 0
0 0 0

4