| Автор: | Иван Кобец | Ограничение времени: | 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
Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке | ||
|---|---|---|---|---|---|---|
| h | w | hi, j | ||||
| 1 | 20 | 2 ≤ h ≤ 3 | 2 ≤ w ≤ 3 | 1 ≤ hi, j ≤ 50 | полная | |
| 2 | 30 | 2 ≤ h ≤ 100 | 2 ≤ w ≤ 100 | 1 ≤ hi, j ≤ 1000 | 1 | полная |
| 3 | 50 | 2 ≤ h ≤ 1000 | 2 ≤ w ≤ 1000 | 1 ≤ hi, j ≤ 109 | 1, 2 | полная |
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 |
|
|