#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;} int W(int x,int y,int w){return (abs(d[x].x-d[y].x)+abs(d[x].y-d[y].y)-1)/w+1-1;} void dijkstra(int x){ dis[1]=0; q.push(mp(0,1)); 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 v=1;v<=n;v++){ w=W(u,v,x); //cout<<v<<" "<<w<<" "<<dis[u]<<" "<<dis[v]<<endl; if(!vis[v]&&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].x)+abs(d[i].y-d[j].y))/mid;//cout<<abs(d[i].x-d[j].x)+abs(d[i].y-d[j].y)<<" "<<mid<<" "<<w<<" "; // if((abs(d[i].x-d[j].x)+abs(d[i].y-d[j].y))%mid)w++;w--; // //cout<<i<<" "<<j<<" "<<w<<endl; // 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(mid); //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=n*2; //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; }