#include #include using ll = long long; #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) #define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i) #define repc2(i, s, n) for (int i = (s); i <= (int)(n); ++i) constexpr int inf = 2000'000'000; constexpr ll linf = 4000000000000000000ll; constexpr ll M7 = 1000000007ll; constexpr ll M09 = 1000000009ll; constexpr ll M9 = 998244353ll; #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) using namespace std; using namespace atcoder; template inline ostream& operator<<(ostream& os, vector& v) { for (auto& e : v) os << e << " "; return os; } template std::ostream& operator<<(std::ostream& os, const std::pair& p) noexcept { return os << "(" << p.first << ", " << p.second << ")"; } #ifdef ONLINE_JUDGE #define debug(...) #else #define debug(...) cerr << "<" << #__VA_ARGS__ << ">: ", debug_out(__VA_ARGS__) template void debug_out(T t) { cerr << t << endl; } template void debug_out(T t, Args... args) { cerr << t << ", "; debug_out(args...); } #endif template struct BIT { private: int n, n_; vector data[2]; void add_(int p, int i, T x) { for (; i < n_; i += (i & -i)) data[p][i] += x; } T sum_(int p, int i) { T s(0); for (; i > 0; i -= (i & -i)) s += data[p][i]; return s; } T sum__(int i) { return sum_(0, i + 1) + sum_(1, i + 1) * (i + 1); } public: BIT(int n) : n(n), n_(n + 1) { data[0].resize(n_, 0); data[1].resize(n_, 0); } BIT() {} void add(int l, int r, T x) { assert(0 <= l && l < r && r <= n); add_(0, l + 1, -x * l); add_(0, r + 1, x * r); add_(1, l + 1, x); add_(1, r + 1, -x); } void add(int i, T x) { assert(0 <= i && i < n); add(i, i + 1, x); } T sum(int l, int r) { assert(0 <= l && l < r && r <= n); return sum__(r - 1) - sum__(l - 1); } T get(int i) { assert(0 <= i && i < n); return sum__(i) - sum__(i - 1); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; using P = pair; P _s, _g; cin >> _s.first >> _s.second >> _g.first >> _g.second; P s = {_s.first - _s.second, _s.first + _s.second}; P g = {_g.first - _g.second, _g.first + _g.second}; int minX = min(s.first, g.first), minY = min(s.second, g.second); vector

v(n); rep(i, n) { int a, b; cin >> a >> b; v[i] = {a - b, a + b}; minX = min(minX, v[i].first); minY = min(minY, v[i].second); } rep(i, n) { v[i].first -= minX; v[i].second -= minY; } s.first -= minX; s.second -= minY; g.first -= minX; g.second -= minY; int maxX = max(s.first, g.first), maxY = max(s.second, g.second); rep(i, n) { maxX = max(maxX, v[i].first); maxY = max(maxY, v[i].second); } vector vx, vy; auto [sx, sy] = s; auto [gx, gy] = g; vx.push_back(s.first); vx.push_back(g.first); vy.push_back(s.second); vy.push_back(g.second); rep(i, n) { auto [x, y] = v[i]; if (s.first <= x && x <= g.first) vx.push_back(x); if (s.second <= y && y <= g.second) vy.push_back(y); } sort(all(vx)); sort(all(vy)); vx.erase(unique(all(vx)), vx.end()); vy.erase(unique(all(vy)), vy.end()); auto cmp = [&](int p) { struct edge { int to, cost; edge(int to, int cost) : to(to), cost(cost) {} }; vector> G(n + 2); const int si = n, gi = n + 1; rep(i, n) { rep(j, n) { if (i == j) continue; auto [x1, y1] = v[i]; auto [x2, y2] = v[j]; int d = max((abs(x2 - x1) + p - 1) / p - 1, (abs(y2 - y1) + p - 1) / p - 1); G[i].emplace_back(j, d); G[j].emplace_back(i, d); } } rep(i, n) { auto [x, y] = v[i]; int sd = max((abs(x - sx) + p - 1) / p - 1, (abs(y - sy) + p - 1) / p - 1); G[si].emplace_back(i, sd); G[i].emplace_back(si, sd); int gd = max((abs(x - gx) + p - 1) / p - 1, (abs(y - gy) + p - 1) / p - 1); G[gi].emplace_back(i, gd); G[i].emplace_back(gi, gd); } auto dijkstra = [&](int ip) { using P = pair; priority_queue, greater

> pq; vector d(G.size(), inf); d.at(ip) = 0; pq.emplace(0ll, ip); while (!pq.empty()) { auto u = pq.top(); pq.pop(); if (u.first > d.at(u.second)) continue; for (const auto& eg : G.at(u.second)) { if (d.at(eg.to) > d.at(u.second) + eg.cost) { d.at(eg.to) = d.at(u.second) + eg.cost; pq.emplace(d.at(eg.to), eg.to); } } } return d; }; auto d = dijkstra(si); return d.at(gi) <= k; }; auto bsearch = [&]() { ll ok = 10000000, ng = 0; while (abs(ng - ok) > 1) { ll mid = (ng + ok) / 2; if (cmp(mid)) ok = mid; else ng = mid; } return ok; }; cout << bsearch() << "\n"; return 0; }