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