Задача 6. Скалолаз

Автор:Иван Кобец   Ограничение времени:3 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Артем с раннего детства увлекается скалолазанием. Сегодня он решил покорить крупный горный хребет в своем городе.

Горный хребет представлен прямоугольником размером h × w метров. Каждая гора на этом хребте занимает квадрат 1 × 1 метр. Гора с координатами (x; y) имеет высоту hy,x метров. Чтобы перебираться между горами, Артём использует канат. Для того, чтобы перебраться с горы x,y на гору i,j, длина каната должна быть большей или равной разнице высот двух гор.

Двигаться Артем может только на соседние по горизонтали или вертикали горы.

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

Формат входных данных

В первой строке записано два натуральных числа h и w — размеры горного хребта. В следующих h строках записано по w чисел hi, j — высоты гор.

Формат выходных данных

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

Ограничения

2 ≤ h, w ≤ 1000

1 ≤ hi, j ≤ 109

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
hwhi, j
1202 ≤ h ≤ 32 ≤ w ≤ 31 ≤ hi, j ≤ 50полная
2302 ≤ h ≤ 1002 ≤ w ≤ 1001 ≤ hi, j ≤ 10001полная
3502 ≤ h ≤ 10002 ≤ w ≤ 10001 ≤ hi, j ≤ 1091, 2полная

Примеры тестов

Стандартный вход Стандартный выход
1
3 3
4 9 7
6 8 1
8 1 1
2

0.126s 0.017s 15