Returning Home
Contest: Codeforces Round 675 (Div. 2)
Difficulty rating: 2300
Tags: graphs, shortest paths, sortings

Yura has been walking for some time already and is planning to return home. He needs to get home as fast as possible. To do this, Yura can use the instant-movement locations around the city.

Let's represent the city as an area of $$$n \times n$$$ square blocks. Yura needs to move from the block with coordinates $$$(s_x,s_y)$$$ to the block with coordinates $$$(f_x,f_y)$$$. In one minute Yura can move to any neighboring by side block; in other words, he can move in four directions. Also, there are $$$m$$$ instant-movement locations in the city. Their coordinates are known to you and Yura. Yura can move to an instant-movement location in no time if he is located in a block with the same coordinate $$$x$$$ or with the same coordinate $$$y$$$ as the location.

Help Yura to find the smallest time needed to get home.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ — the size of the city and the number of instant-movement locations ($$$1 \le n \le 10^9$$$, $$$0 \le m \le 10^5$$$).

The next line contains four integers $$$s_x$$$ $$$s_y$$$ $$$f_x$$$ $$$f_y$$$ — the coordinates of Yura's initial position and the coordinates of his home ($$$ 1 \le s_x, s_y, f_x, f_y \le n$$$).

Each of the next $$$m$$$ lines contains two integers $$$x_i$$$ $$$y_i$$$ — coordinates of the $$$i$$$-th instant-movement location ($$$1 \le x_i, y_i \le n$$$).

Output format:
In the only line print the minimum time required to get home.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example Yura needs to reach $$$(5, 5)$$$ from $$$(1, 1)$$$. He can do that in $$$5$$$ minutes by first using the second instant-movement location (because its $$$y$$$ coordinate is equal to Yura's $$$y$$$ coordinate), and then walking $$$(4, 1) \to (4, 2) \to (4, 3) \to (5, 3) \to (5, 4) \to (5, 5)$$$.

Example input:
5 3
1 1 5 5
1 2
4 1
3 3

Example output:
5

Example input:
84 5
67 59 41 2
39 56
7 2
15 3
74 18
22 7

Example output:
42

Editorial:
You can build a graph with vertices at the start point and all fast travel points. The distance between the vertices $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is calculated as $$$ min (|x_1 - x_2|, |y_1 - y_2|)$$$. To avoid drawing all $$$m * (m + 1) / 2$$$ edges in the graph, note that for a pair of points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ such that $$$|x_1 - x_2| \le |y_1 - y_2|$$$, if there is a point with coordinate $$$x_3$$$ such that it is between $$$x_1$$$ and $$$x_2$$$ ($$$min (x_1, x_2) \le x_3 \le max (x_1, x_2)$$$), then the distance between the first and second point will be equal to the sum of the distances between the first and third and between the third and second. In this case, the edge between the first and second points does not need to be drawn  – it will be unnecessary. It turns out that for each point of the graph it will be enough to draw the edges to the points nearest along the $$$x$$$ axis in both directions. Similarly for $$$y$$$. Next, in the constructed graph, we find the minimum distance from the starting point to each point of the graph $$$(x, y)$$$ and sum it up with the distance to the end point $$$(f_x, f_y)$$$, which is equal to $$$|x - f_x| + |y - f_y|$$$. Among all the distances, we choose the minimum one.