题目描述

丹尼是 Dungeon Crawlers 的狂热粉丝。最近，他想知道电脑是否可以玩这个游戏，而他想让你帮他试一试。

游戏分为 $L$ 个关卡，每个关卡都有 $N\times M$ 个单元格。单元格有以下几种：

• 0 代表一个空单元格。

• -1 代表通往下一个关卡的出口，进入下一关后初始位置在这个出口的位置，除了最后一关没有出口，每个关卡都只有一个出口。

• -9 代表无法通过的障碍物。

• x 一个整数 $x(1\leq x\leq 10^9)$ ，代表敌人的能力值。

为了击败敌人，你的能力值需要大于或等于它的能力值。打败它后，你自己的能力值就会增加与被击败的敌人的能力值相等的值。你可以走上下左右四个单元格，有敌人的格子必须击败才能通过。出口是强制传送的，不能经过出口而不传送。

假设初始的能力值为 $1$，你从地牢第一层左上角的 $(1,1)$ 开始，在最后一层的任意位置结束游戏。那么你能达到的最大能力值是多少？数据保证始终存在一条通往最后一关的路径。

输入格式

第一行三个整数 $L,N,M$。

接下来 $L$ 个矩阵，每个矩阵有 $N$ 行 $M$ 列共 $N\times M$ 个整数表示单元格的种类。

保证 $(1,1)$ 位置上数为 $0$。

输出格式

一个整数表示答案。

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

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq L\times N\times M\leq 10^6$。

说明

翻译自 AGM 2022 Qualification Round B Dungeon。