DijkstraHeap<int>h;
h.malloc(1d6,1);
ll@n;
rep(n){
	ll@x,@y;
	h.change(y*1d3+x,0);
}
char f[1d3][1d3]{};
ll@m;
rep(m){
	ll@z,@w;
	f[w][z]=1;
}
while(1){
	ll a=h.pop();
	ll v=h.val[a];
	ll y=a/1d3;
	ll x=a%1d3;
	if(f[y][x]){
		wt(v);
		exit(0);
	}
	if(y)     h.change(a-1d3,v+1);
	if(y<999) h.change(a+1d3,v+1);
	if(x)     h.change(a-1,v+1);
	if(x<999) h.change(a+1,v+1);
}