#include<bits/stdc++.h> #define Rf(i,a,b) for(int i=(a);i<=(b);i++) #define Rb(i,a,b) for(int i=(a);i>=(b);i--) #define ll long long using namespace std; const int N=1510; ll d[N];ll INF=1e18+10; ll x[N],y[N]; struct nd{ int id;ll vl; bool operator<(const nd &b)const{ return vl>b.vl; } };priority_queue<nd> q; ll dis(int i,int j){ return abs(x[i]-x[j])+abs(y[i]-y[j]); } int k;int n,m,X; bool vis[N]; void dij(){ while(!q.empty()) q.pop(); Rf(i,1,m) d[i]=INF,vis[i]=0; d[1]=0;q.push((nd){1,0}); while(!q.empty()){ nd now=q.top();q.pop(); if(vis[now.id]) continue; vis[now.id]=1; Rf(i,1,m){ if(i==now.id) continue; if(vis[i]) continue; ll dist=dis(now.id,i); dist=(dist+k-1)/k-1; if(now.vl+dist<d[i]){ d[i]=now.vl+dist;q.push((nd){i,now.vl+dist}); } } } } int main(){ cin>>n>>m>>X; int xa,ya,xb,yb;cin>>xa>>ya>>xb>>yb; x[1]=xa,y[1]=ya; Rf(i,1,m) cin>>x[i+1]>>y[i+1]; x[m+2]=xb,y[m+2]=yb; int l=1,r=n*2;m+=2; while(l<r){ int mid=(l+r)/2;k=mid; dij();//cout<<d[m]<<' '; if(d[m]<=1ll*X) r=mid; else l=mid+1; //cout<<l<<' '<<r<<endl; }cout<<l; return 0; }