Задача B. Новое заклинание ≡

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб выучил новое заклинание. Теперь Хоттабыч может проходить через стены. Хоттабыч знает, что в доме, где живёт его друг Волька, N этажей. На каждом этаже по M квартир, при этом все квартиры одинаковые по размерам. В этом доме номер квартиры состоит из двух чисел — номер этажа и номер квартиры на этаже. На каждом этаже квартиры нумеруются одинаково. То есть для квартиры с номером (i; j) квартиры с номерами (i; j − 1) и (i; j + 1) будут соответственно соседними слева и справа, а квартиры (i − 1; j) и (i + 1; j) — снизу и сверху.

Волька живёт в квартире с номером (V_i; V_j), а Волькин друг в квартире (F_i; F_j). Хоттабыч хочет из квартиры Вольки добраться до квартиры его друга, применяя новое заклинание. Находясь в любой квартире, Хоттабыч может перейти в соседнюю квартиру (слева, справа, снизу, сверху), при этом, в зависимости от некоторых особенностей той квартиры, куда пойдёт Хоттабыч, у него будет либо отниматься, либо прибавляться магическая энергия. Для каждой квартиры этого дома Хоттабыч знает на сколько измениться его энергия, при появлении в ней (если число положительное, то столько энергии прибавляется, если же оно отрицательное, то энергия уменьшается на модуль этого числа).

Предоставив вам все необходимые данные, Хоттабыч просит вас написать программу, которая бы рассчитывала минимальные затраты или максимальный прирост магической энергии Хоттабыча при переходе из квартиры (V_i; V_j) в квартиру (F_i; F_j). В случае прироста ответ будет отрицательным. Также Хоттабыч не хочет, чтобы по пути, при переходе через одну стенку, у него отнималось больше 10⁶ единиц энергии.

Формат входного файла

Формат выходного файла

•  − 1 − 1, если Хоттабыч не сможет добраться с квартиры Вольки в квартиру его друга
•  − 2 − 2, если по пути Хоттабыч сможет получить бесконечно большой прирост энергии
• Минимальные затраты энергии — в противном случае.

Ограничения

1 ≤ N, M ≤ 650

 − 1000001 ≤ a(i; j) ≤ 1000000

Примеры тестов

2 2 1 1 2 2
-1 -3
-2 -4
  

6

3 3 3 3 1 1
-1 -1 -1
-1  5  2
-1  4  3
  

-2 -2

3 3 3 3 1 1
      -1 -1000001 -1
-1000001       -1  2
      -1        4  3
  

-1 -1

3 4 2 2 2 3
-20 -20 -20 -20
-20 -20  13 -20
-20 -20 -20 -20
  

-13