#include<bits/stdc++.h> #define int long long using namespace std; int n,m,s,x[1005],y[1005],d[1005]; bool vis[1005]; int dis(int a,int b){ return abs(x[a]-x[b])+abs(y[a]-y[b]); } void dij(int k){ priority_queue<pair<int,int>>q; q.push({0,0}); while(q.size()){ int now=q.top().second; // cout<<now<<endl; q.pop(); if(vis[now])continue; vis[now]=1; for(int i=0;i<=m+1;i++){ if(i==now)continue; // cout<<i<<" "<<(dis(i,now)-1)/k+d[now]<<" "<<dis(i,now)<<endl; if((dis(i,now)-1)/k+d[now]<d[i]){ int di=(dis(i,now)-1)/k+d[now]; d[i]=di; q.push({-di,i}); } } } } bool check(int k){ for(int i=0;i<=m+1;i++)vis[i]=0,d[i]=2e9; d[0]=0; dij(k); // cout<<k<<" "; // for(int i=0;i<=m+1;i++)cout<<d[i]<<" "; // cout<<endl; return d[m+1]<=s; } void read(int &x){ x=0; bool f=0; char c=getchar(); while(!isdigit(c)){ if(c=='-')f=1; c=getchar(); } while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); } if(f)x=-x; return; } signed main(){ //freopen("road.in","r",stdin); //freopen("road.out","w",stdout); read(n),read(m),read(s),read(x[0]),read(y[0]),read(x[m+1]),read(y[m+1]); for(int i=1;i<=m;i++)read(x[i]),read(y[i]); int l=1,r=n+n,mid; // cout<<check(50)<<endl; while(l<r){ mid=l+r>>1; if(check(mid))r=mid; else l=mid+1; } cout<<l<<endl; return 0; }