04. Pereprava

— Ого!
Примерно так переводятся на литературный язык многочисленные "ничоси!", "фигасе!" и прочие междометия, взмывшие над колонной роботов-туристов, внезапно вышедшей к реке.

— Переходить будем вброд! — заявил гид. — Вы ж хотели приключений? Да не переживайте: этот участок реки неглубокий, тщательно промеренный. Вот карта: тут проставлены глубины в робометрах с интервалом 1 робошаг. А вот за пределами этого участка глубоко, не пройти.

Туристы озабоченно уставились на листок, на котором было написано M строк по N чисел. Первая строка содержала глубины в шаге от берега, следуюшая - в двух шагах и т.д., последняя - глубины у противоположного берега. Да, вроде не глубоко, а если идти по одному и не по прямой, так и вообще мелко... Конструктивные особенности роботов-туристов не позволяют им поворачивать в воде (фронтальные их стороны должны были быть обращены к противоположному берегу), но робот способен выполнять шаги вперёд, вправо и влево. Рост роботуристов достаточен для преодоления данной водной преграды без полного погружения.

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

Входные данные. В первой строке разделённые пробелом натуральные числа M и N, оба они не больше 100. Далее следуют М строк по N разделённых пробелами натуральных чисел - глубины (известно, что они точно меньше 1000 робометров).

Выходные данные. Натуральное число - высота мокрой части роботуристов при условии, что они постараются её минимизировать.

Пример. При входных данных
3 4
9 1 7 4
2 4 6 8
3 5 1 5
результатом работы программы будет число 4. Путь их будет пролегать через точки с глубинами 1, 4, 2, 3.