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