Юра в свой выходной достаточно уже погулял по городу и решил возвращаться домой. Чтобы возвращение домой прошло безопасно, ему нужно вернуться как можно быстрее. А для этого Юра будет использовать точки быстрого перемещения, которые расположены по всему городу.
Давайте расчертим весь город на \(n \times n\) квадратных регионов. Юре нужно добраться из региона с координатами \((s_x,s_y)\) в регион с координатами \((f_x,f_y)\). За одну минуту Юра может переместиться в любой соседний по стороне регион, то есть он может двигаться в четырех направлениях. Также в городе есть \(m\) точек для быстрого перемещения. Их координаты вам (и Юре, конечно) известны. Юра может мгновенно переместиться к точке быстрого перемещения, если сейчас он находится в клетке с той же самой координатой по \(x\) или по \(y\).
Помогите Юре посчитать, какое минимальное время потребуется ему для возвращения домой.
Выходные данные
В единственной строке выведите минимальное время для возвращения домой.
Примечание
В первом примере Юра должен попасть в \((5, 5)\) из \((1, 1)\). Он может это сделать за \(5\) минут, сначала использовав вторую точку быстрого перемещения (потому что ее \(y\) координата равна \(y\) координате Юры), а затем пройдя пешком \((4, 1) \to (4, 2) \to (4, 3) \to (5, 3) \to (5, 4) \to (5, 5)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 1 5 5
1 2
4 1
3 3
|
5
|
|
2
|
84 5
67 59 41 2
39 56
7 2
15 3
74 18
22 7
|
42
|