Ремонт
Ремонт у Васи дома затянулся. Теперь весь пол в Васином коридоре засыпан пылью. Причем совсем не равномерно. Кое-где Вася пытался начать подметать пол, но, устрашившись размеров коридора, благоразумно решил забросить это гиблое дело.
Петя решил зайти к Васе поиграть в гиперкости. Так что Васе надо найти игру, которую он бросил в коридоре. Пол Васиного коридора выложен плиткой и представляет собой прямоугольник размером 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, n ≤ 30), а также координаты клеток A_1, B_1, A_2,B_2 (0 < A_1, A_2 ≤ m, 0 < B_1, B_2 ≤ n).
Каждая из следующих n строк содержит m чисел от 1 до 9, определяющих класс соответствующей плитки.
Выходные данные
Выведите минимальное время (в секундах), необходимое Васе, чтобы добраться до игры.