Ремонт#4243
Ремонт у Васі вдома затягнувся. Тепер уся підлога у Васіному коридорі засипана пилом. Причому зовсім не рівномірно. Десь Вася пробував починати підмітати підлогу, але, злякавшись розмірів коридору, завбачливо вирішив покинути цю безнадійну справу.
Петя вирішив зайти до Васі пограти у гіперкамені. Так що Васі потрібно знайти гру, яку він кинув у коридорі. Підлога Васіного коридору викладена плиткою і являє собою прямокутник розміром на . Вася стоїть на плитці з координатами (A_1, B_1), а гра знаходиться на плитці (A_2, B_2).
Вася хоче якомога швидше дістатися до гри, проте він не хоче піднімати пил або розносити його по тим місцям, які він уже колись підмітав. Тому чим більше пилу на плитці, тим повільніше Вася буде по ній йти. Знаючи, скільки днів він не підмітав кожну з плиток, Вася розподілив плитки по класах від до . Таким чином, щоб подолати плитку класу , Васі знадобиться секунд. Крім того, перед тим як зійти з бруднішої плитки k_1 на чистішу k_2 (k_1 > k_2) і не рознести при цьому пил, Вася буде струшувати свої тапки рівно (k_1 - k_2) секунд. Щоб не збитися, Вася буде переходити з плитки на плитку лише якщо вони дотикаються сторонами.
Цікаво, скільки часу потрібно Васі, щоб дістатися до гри?
У першому рядку вхідного файлу містяться числа , (0 < m, n \leq 30), а також координати клітинок A_1, B_1, A_2, B_2 (0 < A_1, A_2 \leq m, 0 < B_1, B_2 \leq n).
Кожен із наступних рядків містить чисел від до , які визначають клас відповідної плитки.
Виведіть мінімальний час (у секундах), необхідний Васі, щоб дістатися до гри.
Приклад 1