#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int m,x;ll dis[maxn]; bool vis[maxn]; struct node { int x,y; }d[maxn]; bool chk(ll K){if(!K)return 0; priority_queue<pair<ll,int> >q; up(i,2,m+2)dis[i]=1e18,vis[i]=0; dis[1]=0,vis[1]=0,q.push(m_p(0,1)); while(!q.empty()){ int x=q.top().p2;q.pop(); if(vis[x])continue;vis[x]=1; up(i,1,m+2){ if(i==x)continue; ll f=(abs(d[x].x-d[i].x)+abs(d[x].y-d[i].y)-1)/K; if(dis[i]>dis[x]+f){ dis[i]=dis[x]+f,q.push(m_p(-dis[i],i)); } } }return (dis[2]<=x); }void slv(){ read();m=read(),x=read(); d[2].x=read(),d[2].y=read(); d[1].x=read(),d[1].y=read(); up(i,3,m+2)d[i].x=read(),d[i].y=read(); ll l=-1,r=2e9; while(l+1<r){ ll mid=l+r>>1; if(chk(mid))r=mid; else l=mid; }cout<<r; }int main(){ //freopen("road.in","r",stdin); //freopen("road.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }