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×nn×n square blocks. Yura needs to move from the block with coordinates (sx,sy)(sx,sy) to the block with coordinates (fx,fy)(fx,fy). In one minute Yura can move to any neighboring by side block; in other words, he can move in four directions. Also, there are mm 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 xx or with the same coordinate yy as the location.
Help Yura to find the smallest time needed to get home.
Input
The first line contains two integers nn and mm — the size of the city and the number of instant-movement locations (1≤n≤1091≤n≤109, 0≤m≤1050≤m≤105).
The next line contains four integers sxsx sysy fxfx fyfy — the coordinates of Yura's initial position and the coordinates of his home (1≤sx,sy,fx,fy≤n1≤sx,sy,fx,fy≤n).
Each of the next mm lines contains two integers xixi yiyi — coordinates of the ii-th instant-movement location (1≤xi,yi≤n1≤xi,yi≤n).
Output
In the only line print the minimum time required to get home.
Examples
Input
5 3 1 1 5 5 1 2 4 1 3 3
Output
5
Input
84 5 67 59 41 2 39 56 7 2 15 3 74 18 22 7
Output
42
Note
In the first example Yura needs to reach (5,5)(5,5) from (1,1)(1,1). He can do that in 55 minutes by first using the second instant-movement location (because its yy coordinate is equal to Yura's yy coordinate), and then walking (4,1)→(4,2)→(4,3)→(5,3)→(5,4)→(5,5)(4,1)→(4,2)→(4,3)→(5,3)→(5,4)→(5,5).
題意：
有一個n * n的網格，一個人要從(sx, sy)去往(fx, fy)，網格中有一些點是特殊點，與特殊點在同一行或同一列上的點，可以直接到達特殊點，花費為0，從任何一個點都可以上下左右移動，每移動一格花費1，問最少花費多少。
思路:
把特殊點所在的行和列當作點
（1）特殊點向它們所在的行和列連雙向邊，花費都為0（特殊點到列為0因為本來就在該行該列，列到特殊點為0因為可以直接到特殊點）；
（2）起點向它所在的行列連邊
（3）出現的行之間連雙向邊，花費為兩行之間的距離。假如出現了x個行數，共連x - 1條邊（兩兩連邊沒有必要並且會炸掉你的邊集陣列導致RE）
遍歷一遍特殊點，答案就是min(起點到特殊點的最短路 + 從特殊點走到終點)
（當然還可能從起點直接走到終點，別忘了取min
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 7;
const ll M = 8e5 + 7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll head[N];
bool vis[N];
ll dis[N];
ll n, m, tot;
struct node {
ll x, y;
}s[N];
struct Node {
ll u, v, l, next;
}edge[M];
struct A{
ll pos, cost;
bool operator < (const A &a)const {
return cost > a.cost;
}
};
void init() {
tot = 1;
memset(head, -1, sizeof(head));
}
void addedge(ll x, ll y, ll z) {
edge[tot].u = x;
edge[tot].v = y;
edge[tot].l = z;
edge[tot].next = head[x];
head[x] = tot++;
}
void dijk(ll src) {
memset(dis, inf, sizeof(dis));
memset(vis, 0, sizeof(vis));
priority_queue<A>q;
dis[src] = 0;
A now;
now.cost = 0;
now.pos = src;
q.push(now);
while(!q.empty()) {
now = q.top();
q.pop();
if(vis[now.pos])
continue;
vis[now.pos] = 1;
for(ll i = head[now.pos]; ~i; i = edge[i].next) {
ll to = edge[i].v;
if(!vis[to] && dis[to] > edge[i].l + dis[edge[i].u]) {
dis[to] = dis[edge[i].u] + edge[i].l;
now.cost = dis[to];
now.pos = to;
q.push(now);
}
}
}
}
ll stx[N], sty[N], totx, toty;
int main() {
init();
totx = 0, toty = 0;
scanf("%lld%lld", &n, &m);
for(ll i = 1; i <= m + 2; ++i) {
scanf("%lld%lld", &s[i].x, &s[i].y);
stx[++totx] = s[i].x;
sty[++toty] = s[i].y;
}
sort(stx + 1, stx + totx + 1);
totx = unique(stx + 1, stx + totx + 1) - stx - 1;
sort(sty + 1, sty + toty + 1);
toty = unique(sty + 1, sty + toty + 1) - sty - 1;
n = m + 2;
map<ll, ll>mx, my;
for(ll i = 1; i <= totx; ++i) {
mx[stx[i]] = ++n;
if(i > 1) {
ll x = stx[i], y = stx[i - 1];
addedge(mx[x], mx[y], abs(x - y));
addedge(mx[y], mx[x], abs(x - y));
}
}
for(ll i = 1; i <= toty; ++i) {
my[sty[i]] = ++n;
ll x = sty[i], y = sty[i - 1];
addedge(my[x], my[y], abs(x - y));
addedge(my[y], my[x], abs(x - y));
}
addedge(1, mx[s[1].x], 0);
addedge(1, my[s[1].y], 0);
for(ll i = 3; i <= m + 2; ++i) {
addedge(i, mx[s[i].x], 0);
addedge(mx[s[i].x], i, 0);
addedge(i, my[s[i].y], 0);
addedge(my[s[i].y], i, 0);
}
dijk(1);
ll minn = inf;
for(ll i = 3; i <= m + 2; ++i) {
minn = min(minn, dis[i] + abs(s[2].x - s[i].x) + abs(s[2].y - s[i].y));
}
minn = min(minn, abs(s[2].x - s[1].x) + abs(s[2].y - s[1].y));
printf("%lld\n", minn);
mx.clear(), my.clear();
return 0;
}