int@n,@k,x[n+2],y[];
rd((x,y)(n+2));
DijkstraHeap<int>h;
h.malloc(n+2);
wt(bsearch_min[int,p,1,2d5][
	h.init(n+2);
	h.change(0,0);
	while(h.size){
		int i=h.pop();
		if(i==1){
			break;
		}
		rep(j,n+2){
			h.change(j,h.val[i]+(abs(y[j]-y[i])+abs(x[j]-x[i])-1)/p);
		}
	}
](h.val[1]<=k));