thlicey1: Тренировка

Петя радостно принял из рук почтальона посылку и сразу же принялся её распаковывать.

- Это первая трёхмерная спелеологическая карта, - сказал Петя, - она полностью передаёт внешний вид пещеры Ласко, которая находится на территории современной Франции.

- Интересно, как быстро можно добраться до самого отдалённого участка пещеры? - спросил Вася.

Петя задумался. Сразу такую задачу решить не по силам, но можно внести модель пещеры в компьютер и вычислить ответ программно.

По заданной карте пещеры (размера \(N \times M \times L\)) найдите самый быстрый путь до самой дальней точки пещеры. Поскольку трёхмерную карту нельзя нарисовать на одном листке бумаги, карта представляет собой \(L\) листков бумаги, на каждый из которых нанесена сетка размера \(N \times M\) (таким образом получаются как бы горизонтальные срезы пещеры).

Учтите, что каждая клетка имеет метку, которая соответствует времени, которое нужно затратить, чтобы пройти по ней. Также есть непроходимые клетки - стены. За пределы карты пещеры выходить нельзя (клетки, лежащие вне карты, являются непроходимыми клетками - стенами).

Из каждой клетки, можно пройти в соседние, если они не являются непроходимыми. Соседними считаются клетки, имеющие общую грань. Учтите, что спелеолог может перемещаться вверх и вниз по горизонтальным разрезам (поскольку обладает альпинистским оборудованием), но для этого нужно, чтобы в соседней клетке находилась стена (непроходимая клетка, либо граница лабиринта). Таким образом, спелеолог не может находиться в клетке, которая не имеет соседних (иначе бы он упал и расшибся). Гарантируется, что спелеолог может безопасно начать свой маршрут (клетка входа в пещеру имеет соседние клетки-стены), а также, что может пройти дальше клетки входа.

Самой дальней клеткой пещеры является клетка, до которой может добраться спелеолог, при этом декартово расстояние от этой клетки до клетки со входом в лабиринт максимально. Если таких клеток несколько - выбрать ту, до которой можно быстрее добраться.