Problem Description

Danny is a hardcore fan of Dungeon Crawlers. Recently, he wanted to know whether a computer can play this game, and he wants you to help him test it.

The game has $L$ levels. Each level contains $N\times M$ cells. A cell can be one of the following types:

• 0 represents an empty cell.

• -1 represents an exit to the next level. After entering the next level, your initial position is at the location of this exit. Except for the last level which has no exit, each level has exactly one exit.

• -9 represents an impassable obstacle.

• x is an integer $x(1\leq x\leq 10^9)$, representing an enemy's power value.

To defeat an enemy, your power value must be greater than or equal to its power value. After defeating it, your own power value increases by an amount equal to the defeated enemy's power value. You may move to the four adjacent cells (up, down, left, right). If a cell contains an enemy, you must defeat it to pass through. Exits are forced teleports: you cannot step onto an exit without being teleported.

Assume your initial power value is $1$. You start from $(1,1)$ at the top-left corner of the first level, and you finish the game at any position on the last level. What is the maximum power value you can reach? The testdata guarantees that there is always a path to the last level.

Input Format

The first line contains three integers $L, N, M$.

Then follow $L$ matrices. Each matrix has $N$ rows and $M$ columns, consisting of $N\times M$ integers describing the type of each cell.

It is guaranteed that the value at position $(1,1)$ is 0.

Output Format

Output one integer, representing the answer.

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

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\leq L\times N\times M\leq 10^6$.

Notes

Translated from AGM 2022 Qualification Round B Dungeon。

Translated by ChatGPT 5