eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ремонт

Ремонт

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Ремонт у Васи дома затянулся. Теперь весь пол в Васином коридоре засыпан пылью. Причем совсем не равномерно. Кое-где Вася пытался начать подметать пол, но, устрашившись размеров коридора, благоразумно решил забросить это гиблое дело.

Петя решил зайти к Васе поиграть в гиперкости. Так что Васе надо найти игру, которую он бросил в коридоре. Пол Васиного коридора выложен плиткой и представляет собой прямоугольник размером n на m. Вася стоит на плитке с координатами (A_1, B_1), а игра находится на плитке (A_2, B_2).

Вася хочет как можно быстрее добраться до игры, однако он не хочет поднимать пыль или разносить ее по тем местам, где он уже когда-то подметал. Поэтому чем больше пыли на плитке, тем медленнее Вася будет по ней идти. Зная, сколько дней он не подметал каждую из плиток, Вася распределил плитки по классам от 1 до 9. Таким образом, чтобы преодолеть плитку класса k, Васе потребуется k секунд. Кроме того, перед тем, как сойти с более грязной плитки k_1 на более чистую k_2 (k_1 >k_2) и не разнести при этом пыль, Вася будет отряхивать свои тапочки ровно (k_1–k_2) секунд. Чтобы не сбиться, Вася будет переходить с плитки на плитку, только если они касаются сторонами.

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

Входные данные

В первой строке входного файла содержатся числа m, n (0 < m, n30), а также координаты клеток A_1, B_1, A_2,B_2 (0 < A_1, A_2 ≤ m, 0 < B_1, B_2n).

Каждая из следующих n строк содержит m чисел от 1 до 9, определяющих класс соответствующей плитки.

Выходные данные

Выведите минимальное время (в секундах), необходимое Васе, чтобы добраться до игры.

Пример

Входные данные #1
6 6 1 1 6 6
1 1 2 3 1 1
1 1 2 2 1 1
1 1 3 2 1 1
2 2 2 2 1 3
2 3 3 1 1 3
1 1 1 1 3 3
Выходные данные #1
18
Источник Orel STU & Udmurt SU Contest, Petrozavodsk, Thursday, September 1, 2005