#include<bits/stdc++.h> #define int long long using namespace std; const int maxm=1007; int n,m,c; struct P{ int x; int y; }Nd[maxm]; int dp[maxm]; inline int dis(P i,P j){ return abs(i.x-j.x)+abs(i.y-j.y); } struct edge{ int v,w; }; struct node{ int id; int dis; }; bool operator>(const node A,const node B){ return A.dis==B.dis?A.id<B.id:A.dis>B.dis; } vector<edge> E[maxm]; int D[maxm]; bool vis[maxm]; bool chk(int k){ priority_queue<node,vector<node>,greater<node> > q; while(!q.empty())q.pop(); for(int i=0;i<=m+1;i++)vis[i]=0; vis[0]=0; for(int i=1;i<=m+1;i++)D[i]=1e12; D[0]=0; if(k==0){ return Nd[0].x==Nd[m+1].x&&Nd[0].y==Nd[0].y; } for(int i=0;i<=m+1;i++){ E[i].clear(); for(int j=0;j<=m+1;j++){ if(j==i)continue; int t=(dis(Nd[i],Nd[j])-1)/k; E[i].push_back((edge){j,t}); } } q.push((node){0,0}); while(!q.empty()){ int u=q.top().id; q.pop(); if(vis[u])continue; vis[u]=1; for(auto e:E[u]){ int v=e.v,w=e.w; if(D[u]+w<D[v]){ D[v]=D[u]+w; q.push((node){v,D[v]}); } } } return D[m+1]<=c; } signed main(){ // freopen("road.in","r",stdin); // freopen("road.out","w",stdout); cin>>n>>m>>c; cin>>Nd[0].x>>Nd[0].y; cin>>Nd[m+1].x>>Nd[m+1].y; for(int i=1;i<=m;i++)cin>>Nd[i].x>>Nd[i].y; int l=0,r=dis(Nd[0],Nd[m+1]); while(l<r){ int mid=l+r>>1; if(chk(mid))r=mid; else l=mid+1; } cout<<l<<endl; }