#include <bits/stdc++.h>
using namespace std;
auto naive = [](int n, int m, int k, auto v) {
auto f = [&](int i, int j) {
auto [x1, y1] = v[i];
auto [x2, y2] = v[j];
auto c1 = [&](int x, int y) {
return x1 <= x && x <= x1 + m && y1 - k <= y && y <= y1 + m + k;
};
auto c2 = [&](int x, int y) {
return x1 - k <= x && x <= x1 + m + k && y1 <= y && y <= y1 + m;
};
if (c1(x2, y2)) return 1;
if (c1(x2, y2 + m)) return 1;
if (c1(x2, y2)) return 1;
if (c1(x2 + m, y2 + m)) return 1;
if (c2(x2, y2)) return 1;
if (c2(x2, y2 + m)) return 1;
if (c2(x2, y2)) return 1;
if (c2(x2 + m, y2 + m)) return 1;
return 0;
};
vector c(n, 0);
auto rec = [&](const auto& self, int cur) -> void {
c[cur] = 1;
for (int nxt = 0; nxt < n; nxt++) {
if (c[nxt]) continue;
if (!f(cur, nxt)) continue;
self(self, nxt);
}
};
rec(rec, 0);
int ret = 0;
for (int i = 0; i < n; i++) {
if (c[i] == 0) continue;
ret = max(ret, v[i][0] + v[i][1] + 2 * m);
}
return ret;
};
auto sol = [](int n, int m, int k, auto v) {
return naive(n, m, k, v);
vector adj(n, vector(0, 0));
for (int iter = 0; iter < 8; iter++) {
vector c(0, 0);
for (int i = 0; i < n; i++) {
c.push_back(v[i][0]);
c.push_back(v[i][0] + m);
}
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
vector in(c.size(), vector(0, 0));
vector out(c.size(), vector(0, 0));
vector buc(c.size(), vector(0, 0));
for (int i = 0; i < n; i++) {
int p1 = lower_bound(c.begin(), c.end(), v[i][0]) - c.begin();
int p2 = lower_bound(c.begin(), c.end(), v[i][0] + m) - c.begin();
in[p1].push_back(i);
out[p2].push_back(i);
buc[p1].push_back(i);
}
set s{ pair(0, 0) }; s.clear();
for (int x = 0; x < c.size(); x++) {
for (int i : in[x]) {
s.insert(pair(v[i][1] + m, i));
}
for (int i : buc[x]) {
if (s.begin()->first >= v[i][1]) continue;
auto it = prev(s.lower_bound(pair(v[i][1], -1)));
if (it->first < v[i][1] - k) continue;
int j = it->second;
adj[i].push_back(j);
adj[j].push_back(i);
}
for (int i : out[x]) {
s.erase(pair(v[i][1] + m, i));
}
}
for (int i = 0; i < n; i++) {
swap(v[i][0], v[i][1]);
v[i][1] = -v[i][1] - m;
if (iter % 4 == 3) v[i][0] = -v[i][0] - m;
}
}
vector c(n, 0);
auto rec = [&](const auto& self, int cur) -> void {
c[cur] = 1;
for (int nxt : adj[cur]) {
if (c[nxt]) continue;
self(self, nxt);
}
};
rec(rec, 0);
int ret = 0;
for (int i = 0; i < n; i++) {
if (c[i] == 0) continue;
ret = max(ret, v[i][0] + v[i][1] + 2 * m);
}
return ret;
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
vector v(n, array{ 0, 0 });
for (int i = 0; i < n; i++) cin >> v[i][0] >> v[i][1];
int k; cin >> k;
cout << sol(n, m, k, v) << '\n';
}
