#include<bits/stdc++.h> using namespace std; #define int long long #define mp make_pair const int M=1010; int n,m,X,dis[M]; bool vis[M]; priority_queue<pair<int,int> >q; struct dot{int x,y;}d[M]; struct Edge{int v,w,nxt;}e[M*M];int CNT,h[M]; void add_side(int u,int v,int w){e[++CNT]=(Edge){v,w,h[u]};h[u]=CNT;} void dijkstra(int x){ dis[x]=0; q.push(mp(0,x)); while(!q.empty()){ int u=q.top().second,v,w;q.pop();//cout<<u<<" "<<h[u]<<endl; if(vis[u])continue; vis[u]=1; for(int i=h[u];i>0;i=e[i].nxt){ v=e[i].v;w=e[i].w; //cout<<v<<" "<<w<<" "<<dis[u]<<" "<<dis[v]<<endl; if(dis[u]+w<dis[v]){ dis[v]=dis[u]+w; q.push(mp(-dis[v],v)); } } } } bool check(int mid){//cout<<mid<<endl; CNT=0; memset(h,0,sizeof(h)); for(int i=1;i<=m+2;i++){ for(int j=i+1;j<=m+2;j++){ int w=(abs(d[i].x-d[j].y)+abs(d[i].y-d[j].y))/mid; if((abs(d[i].x-d[j].y)+abs(d[i].y-d[j].y))%mid)w++;w--; add_side(i,j,w);add_side(j,i,w); } } //for(int i=1;i<=(m+2)*(m+2);i++)e[i]=(Edge){0,0,0}; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); dijkstra(1); //for(int i=1;i<=m+2;i++)cout<<dis[i]<<" "<<h[i]<<endl; //cout<<endl<<endl; return dis[m+2]<=X; } signed main(){ scanf("%lld%lld%lld",&n,&m,&X); scanf("%lld%lld",&d[1].x,&d[1].y); scanf("%lld%lld",&d[m+2].x,&d[m+2].y); for(int i=1;i<=m;i++){scanf("%lld%lld",&d[i+1].x,&d[i+1].y);} if(d[1].x==d[m+2].x&&d[1].y==d[m+2].y){ printf("0"); return 0; } int l=1,r=d[m+2].x+d[m+2].y; //cout<<l<<" "<<r<<endl; while(l<r){ int mid=(l+r)/2; // cout<<mid<<" "<<check(mid)<<endl; if(check(mid))r=mid; else l=mid+1; } printf("%lld",l); return 0; }