В волшебном королевстве Эквилибрия после могущественного заклинания случилась непредвиденная буря, которая затопила земли между Великой библиотекой Эквилибрии и торговым кварталом. Ваш герой, юный маг, должен пройти от библиотеки к рынку, чтобы доставить важные свитки с заклинаниями. Затопленные поля королевства представляют собой сетку размером $$$n \times m$$$, и каждая ячейка сетки содержит воду определённой глубины. Маг может перемещаться только вправо, влево и вниз по сетке ($$$(\mathit{row}, \mathit{col} + 1)$$$, $$$(\mathit{row}, \mathit{col} - 1)$$$ и $$$(\mathit{row} + 1, \mathit{col})$$$), начиная своё путешествие из верхнего левого угла ($$$(1, 1)$$$, библиотека) и заканчивая в нижнем правом ($$$(n, m)$$$, рынок). Ваша задача — найти путь, при проходе по которому максимальная глубина воды будет минимальной, чтобы ваш герой оставался как можно более сухим.
В первой строке даны два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 500$$$) — размеры Эквилибрии. В следующих $$$n$$$ строках даны по $$$m$$$ целых чисел $$$d_{i, j}$$$ ($$$0 \le d_{i, j} \le 10^9$$$, $$$d_{1, 1} = d_{n, m} = 0$$$), обозначающих глубину воды в каждой ячейке.
Выведите максимальную глубину воды на найденном пути.
3 30 1 99 1 99 1 0
1
5 30 1 19 9 21 1 12 9 91 1 0
2
