#include <bits/stdc++.h> #define int long long #define pii pair<int,int> #define mkp make_pair #define fir first #define sec second #define push_back emplace_back using namespace std; int n, m, x, xx[1005], yy[1005]; // vector <pii> ed[1005]; inline int ds(int x, int y, int mid) { int dd = abs(xx[x] - xx[y]) + abs(yy[x] - yy[y]); return dd <= mid ? 0 : ceil(1.0 * dd / mid) - 1; } bool vis[1005]; int dis[1005]; inline bool check(int mid) { priority_queue <pii, vector <pii>, greater <pii>> pq; memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis); dis[1] = 0; pq.push(mkp(0, 1)); while (!pq.empty()) { int u = pq.top().sec; pq.pop(); if (vis[u]) continue; vis[u] = 1; for (int v = 1; v <= m; v++) { if (u == v) continue; if (ds(u, v, mid) + dis[u] < dis[v]) { dis[v] = ds(u, v, mid) + dis[u]; pq.push(mkp(dis[v], v)); } } } return dis[2] <= x; } signed main() { freopen("road.in", "r", stdin); freopen("road.out", "w", stdout); scanf("%lld %lld %lld", &n, &m, &x); m += 2; for (int i = 1; i <= m; i++) { scanf("%lld %lld", &xx[i], &yy[i]); // for (int j = 1; j < m; j++) // { // ed[i].push_back(mkp(j, ds(i, j))); // ed[j].push_back(mkp(i, ds(i, j))); // } } int l = 1, r = n * 2; while (l < r) { int mid = (l + r >> 1); if (check(mid)) { r = mid; } else l = mid + 1; } printf("%lld", l); fclose(stdout); return 0; }