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)(s_x,s_y) to the block with coordinates (fx,fy)(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 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≤109,0≤m≤105)(1≤n≤10^9, 0≤m≤10^5).
The next line contains four integers sx sy fx fys_x\ s_y\ f_x\ f_y — the coordinates of Yura’s initial position and the coordinates of his home (1≤sx,sy,fx,fy≤n)(1≤s_x,s_y,f_x,f_y≤n).
Each of the next mm lines contains two integers xi yix_i\ y_i — coordinates of the ii-th instant-movement location (1≤xi,yi≤n)(1≤x_i,y_i≤n).

Output

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

Examples

input

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

output

1
5

input

1
2
3
4
5
6
7
84 5
67 59 41 2
39 56
7 2
15 3
74 18
22 7

output

1
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).

Translation

给定一个 n×nn\times n 的网格地图，和起点 (sx,sy)(s_x,s_y)，终点 (fx,fy)(f_x,f_y)，人只能向上下左右四个方向走，求起点到终点需要的最短时间，定义走一步时间为 11。给了mm 个瞬移点，如果当前所在位置的 xx 坐标或 yy 坐标等于某个瞬移点的 xx 坐标或 yy 坐标，那么就可以瞬移到这个点。

Idea

如果我们定义起点也为一个瞬移点，那么可以断定：走后的几步，一定会从某个瞬移点徒步走到 (fx,fy)(f_x,f_y)。
显然，瞬移点的数量为 m+1m+1 个，两个瞬移点 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 之间的距离为 min⁡(x1−x2,y1−y2)\min(x_1-x_2,y_1-y_2)。我们可以在瞬移点两两之间建边，然后求最短路，那么就有 (m+1)×(m+2)(m+1)\times(m+2) 条边，这在时间和空间上都是不允许的。
我们需要优化建边。显然，从一个瞬移点 (x1,y1)(x_1,y_1) 走向另一个瞬移点 (x2,y2)(x_2,y_2)，可以有两种较优的方案：从 (x1,y1)(x_1,y_1) 走到 (x2,y1)(x_2,y_1)，称之为从 xx 方向靠近；从 (x1,y2)(x_1,y_2) 走到 (x1,y2)(x_1,y_2) 成为从 yy 方向靠近。如果是从 xx 方向靠近，可以先到 xx 坐标比 x2x_2 小且最大的瞬移点，或 xx 坐标大于 x2x_2 且最小的瞬移点，再走到 (x2,y1)(x_2,y_1)，这样走的就是 (x1,y1)(x_1,y_1) 到 (x2,y2)(x_2,y_2) 的最短路径；若从 yy 方向靠近，同理。
对于一个瞬移点 (x,y)(x,y)，直接向 (x1,yunknown)(x_1,y_{\text{unknown}}) 和 (x2,yunknown)(x_2,y_{\text{unknown}}) 连边。x1x_1 是满足 x1≤xx_1\le x 的最大的瞬移点（除自身外）横坐标，x2x_2 是满足 x2≥xx_2\ge x 的最大的瞬移点（除自身外）坐标；对于 yy 坐标，同理建边。
用 Dijkstra\text{Dijkstra} 算法即可求得起点到各个瞬移点的最短距离，最后枚举每个瞬移点作为最后直接走到 (fx,fy)(f_x,f_y) 的那个瞬移点并更新答案。边的规模是 4×(m+1)4\times (m+1)，时间复杂度 O(mlog⁡m)O(m\log m)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1422D
Date: 10/6/2020
Description: Graph Theory
*******************************************************************/
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<utility>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1000006;
int n,m;
int sx,sy,fx,fy;
int ID[N];
pair<int,int> loc[N];
int head[N];
struct E
{
	int to;
	int Next;
	ll w;
}edge[N<<1];
ll dis[N];
bool vis[N];
int tot;
inline void add_edge(int,int,ll);
void Dijkstra(int);
int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	cin>>sx>>sy>>fx>>fy;
	int i;
	m++;
	//起点是 instant-movement loction
	loc[1]=make_pair(sx,sy);
	ID[1]=1;
	for(i=2;i<=m;i++){
		scanf("%d%d",&loc[i].first,&loc[i].second);
		ID[i]=i;//存排名
	}
	sort(ID+1,ID+1+m,[]
	(const int& a,const int& b){
		//走到x相同的位置
		return loc[a].first<loc[b].first;
	});
	for(i=2;i<=m;i++){
		//x方向相邻建边
		int cost=loc[ID[i]].first-loc[ID[i-1]].first;
		add_edge(ID[i],ID[i-1],cost);
		add_edge(ID[i-1],ID[i],cost);
	}
	sort(ID+1,ID+1+m,[]
	(const int& a,const int& b){
		//走到y相同的位置
		return loc[a].second<loc[b].second;
	});
	for(i=2;i<=m;i++){
		//y方向相邻建边
		int cost=loc[ID[i]].second-loc[ID[i-1]].second;
		add_edge(ID[i],ID[i-1],cost);
		add_edge(ID[i-1],ID[i],cost);
	}
	ll ans=0x3f3f3f3f3f3f3f3f;
	Dijkstra(1);
	//枚举最终的瞬移点
	for(i=1;i<=m;i++){
		ans=min(ans,dis[i]+abs(fx-loc[i].first)+abs(fy-loc[i].second));
	}
	cout<<ans<<endl;
	return 0;
}
inline void add_edge(int u,int v,ll w){
	tot++;
	edge[tot].to=v;
	edge[tot].Next=head[u];
	edge[tot].w=w;
	head[u]=tot;
}
void Dijkstra(int s){
	struct node
	{
		int id;
		ll dis;
		bool operator<(const node& x)const{
			return x.dis<dis;
		}
	};
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	priority_queue<node>q;
	q.push(node{s,0});
	while(!q.empty()){
		node cur=q.top();
		q.pop();
		int x=cur.id;
		if(vis[x]){
			continue;
		}
		vis[x]=1;
		for(register int i=head[x];~i;i=edge[i].Next){
			int y=edge[i].to;
			if(!vis[y]&&dis[y]>dis[x]+edge[i].w){
				dis[y]=dis[x]+edge[i].w;
				q.push(node{y,dis[y]});
			}
		}
	}
}