//80pts #include<bits/stdc++.h> #define int long long using namespace std; int n,m,cost; int xb,yb,xe,ye; pair<int,int>d[1010]; int dis[1010][1010]; queue<pair<int,int> >q; int co[1010]; bool check(int k){ while(!q.empty())q.pop(); memset(co,0x3f,sizeof(co)); q.push(make_pair(1,0)); co[1]=0; while(!q.empty()){ int x=q.front().first,c=q.front().second; if(x==m)return 1; q.pop(); for(int i=2;i<=m;i++){ if(i==x)continue; int cc=(dis[x][i]-1)/k; cc+=c; if(cc<=cost&&co[i]>cc){ co[i]=cc; q.push(make_pair(i,cc)); } } } return 0; } signed main(){ cin>>n>>m>>cost; cin>>xb>>yb>>xe>>ye; for(int i=2;i<=m+1;i++){ cin>>d[i].first>>d[i].second; } m+=2; d[1]=make_pair(xb,yb); d[m]=make_pair(xe,ye); for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ dis[i][j]=abs(d[i].first-d[j].first)+abs(d[i].second-d[j].second); } } int l=1,r=1000000000; while(l!=r){ int mid=(l+r)>>1; if(check(mid)){ r=mid; }else{ l=mid+1; } } cout<<l; return 0; }