#include<bits/stdc++.h> using namespace std; #define int long long const int mmax=2*1e9+10; int n,m,X,now,f[110][110]; struct dot{int x,y;}d[100010]; bool cmp(dot a,dot b){ int da=abs(a.x-d[1].x)+abs(a.y-d[1].y); int db=abs(b.x-d[1].x)+abs(b.y-d[1].y); return da<db; } bool cmp1(dot a,dot b){ int da=abs(a.x-d[now].x)+abs(a.y-d[now].y); int db=abs(b.x-d[now].x)+abs(b.y-d[now].y); } bool check(int mid){ //cout<<endl<<"!"<<mid<<endl; memset(f,0x3f,sizeof(f)); for(int j=0;j<=X;j++)f[1][j]=0; for(int i=2;i<=m+2;i++){ for(int j=0;j<=X;j++){ for(int k=1;k<=m+2;k++){ //cout<<i<<" "<<j<<" "<<k<<endl; int dis=abs(d[i].x-d[k].x)+abs(d[i].y-d[k].y); int p=dis/mid;if(dis%mid)p++;p--;p=max(p,0LL); //cout<<dis<<" "<<p<<" "; if(j>=p){ int q=dis/(p+1);if(dis%(p+1))q++; f[i][j]=min(f[i][j],max(f[k][j-p],q)); }//cout<<f[i][j]<<endl; } //cout<<endl; } //now=i; //sort(d+i+1,d+m+2,cmp1); } int ans=mmax; for(int j=0;j<=X;j++)ans=min(ans,f[m+2][j]); if(ans<=mid)return 1; else return 0; } signed main(){ //freopen("road.in","r",stdin); //freopen("road.out","w",stdout); 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);} sort(d+2,d+m+2,cmp); if(d[1].x==d[m+2].x&&d[1].y==d[m+2].y){ printf("0"); return 0; } int l=1,r=d[m+2].x+d[m+2].y; //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; }