#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template static void amin(T &x, U y) { if (y < x) x = y; } template static void amax(T &x, U y) { if (x < y) x = y; } struct MaxVal { long long val; MaxVal() : val(-INFL) {} explicit MaxVal(long long val) : val(val) {} MaxVal &operator+=(MaxVal that) { amax(val, that.val); return *this; } MaxVal operator+(MaxVal that) const { return MaxVal(*this) += that; } }; using Val = long long; using Sum = MaxVal; //template struct GetRangeRangeTree2D { typedef int Pos; vector > perms; vector poses; vector > nodes; vector > rcnts; int n, log2n; void init(const vector &ys, const Val &v = Val()) { init(ys, vector(ys.size(), v)); } private: struct IndirectPosCmp { const vector &ys; IndirectPosCmp(const vector &ys_) : ys(ys_) { } bool operator()(int i, int j) const { bool a = i >= (int)ys.size(), b = j >= (int)ys.size(); if (a || b) return !a < !b; else return ys[i] < ys[j]; } }; public: void init(const vector &ys, const vector &vals) { n = 1, log2n = 0; while (n < (int)ys.size()) n *= 2, log2n ++; nodes.resize(n * 2); perms.assign(log2n + 1, vector(n)); nodes.assign(log2n + 1, vector(n * 2)); rcnts.assign(log2n, vector(n + 1)); vector prev(n), cnt(n); for (int i = 0; i < n; i ++) { perms[log2n][i] = i; nodes[log2n][n + i] = i < (int)ys.size() ? Sum(vals[i]) : Sum(); cnt[i] = i; } for (int i = n - 1; i > 0; -- i) nodes[log2n][i] = nodes[log2n][i * 2] + nodes[log2n][i * 2 + 1]; vector origin(n); for (int k = log2n - 1; k >= 0; -- k) { prev.swap(cnt); int h = 1 << (log2n - k), h2 = (h - 1) / 2 + 1; vector &cperms = perms[k]; vector &cnodes = nodes[k]; vector &crcnts = rcnts[k]; for (int j = 0; j < n; j += h) { for (int k = 0; k < h; ++ k) origin[prev[j + k]] = k >= h / 2; merge(prev.begin() + j, prev.begin() + j + h / 2 , prev.begin() + j + h / 2, prev.begin() + j + h , cnt.begin() + j, IndirectPosCmp(ys)); for (int i = 0; i < h; i ++) { int p = cnt[j + i]; cperms[p] = j + i; cnodes[j * 2 + h + i] = p < (int)ys.size() ? Sum(vals[p]) : Sum(); crcnts[j + i + 1] = crcnts[j + i] + (origin[p] ? 1 : 0); } for (int i = h - 1; i > 0; -- i) cnodes[j * 2 + i] = cnodes[j * 2 + i * 2] + cnodes[j * 2 + i * 2 + 1]; } } poses.resize(n); for (int i = 0; i < n; ++ i) poses[perms[0][i]] = i < (int)ys.size() ? ys[i] : -1; } Sum getRange(int i1, int j1, Pos i2, Pos j2) const { if (i1 >= j1 || i2 >= j2) return Sum(); int pL = (int)(lower_bound(poses.begin(), poses.end(), i2) - poses.begin()); int pR = (int)(lower_bound(poses.begin() + pL, poses.end(), j2) - poses.begin()); return getRangeRec(0, 1, 0, i1, j1, i2, j2, pL, pR); } void set(int p, const Val &x) { for (int i = p + n, k = log2n; i > 0; i >>= 1, -- k) { int h = 1 << (log2n - k), base = (i - (1 << k)) * h; set1(&nodes[k][base * 2], h, perms[k][p] - base, x); } } private: inline void set1(Sum *cnodes, int h, int i, const Val &x) const { cnodes[h + i] = Sum(x); for (i = (i + h) >> 1; i > 0; i >>= 1) cnodes[i] = sum1(cnodes, h, i * 2) + sum1(cnodes, h, i * 2 + 1); } Sum getRangeRec(int k, int i, int l, int i1, int j1, Pos i2, Pos j2, int pL, int pR) const { if (pL >= pR) return Sum(); int h = 1 << (log2n - k); int base = (i - (1 << k)) * h; if (j1 - i1 == h) { return getRange1(&nodes[k][base * 2], h, pL, pR); } else { int m = l + h / 2; int qL = rcnts[k][base + pL] - rcnts[k][base]; int qR = rcnts[k][base + pR] - rcnts[k][base]; Sum res = Sum(); if (i1 < m) res += getRangeRec(k + 1, i * 2, l, i1, min(j1, m), i2, j2, pL - qL, pR - qR); if (m < j1) res += getRangeRec(k + 1, i * 2 + 1, m, max(i1, m), j1, i2, j2, qL, qR); return res; } } inline Sum getRange1(const Sum *cnodes, int h, int i, int j) const { Sum res = Sum(); for (int l = i + h, r = j + h; l < r; l >>= 1, r >>= 1) { if (l & 1) res += sum1(cnodes, h, l ++); if (r & 1) res += sum1(cnodes, h, -- r); } return res; } inline Sum sum1(const Sum *cnodes, int h, int i) const { return cnodes[i]; } }; struct City { int lat, lon, hei, pts; }; int main() { int n; int xDiff; int yDiff; while (~scanf("%d%d%d", &n, &xDiff, &yDiff)) { vector cities(n); rep(i, n) { int A; int B; int C; int D; scanf("%d%d%d%d", &A, &B, &C, &D); cities[i] = { A, B, C, D }; } sort(cities.begin(), cities.end(), [](City a, City b) { return a.hei < b.hei; }); vector> xis(n); rep(i, n) xis[i] = { cities[i].lat, i }; sort(xis.begin(), xis.end()); vector ys(n); rep(i, n) ys[i] = cities[xis[i].second].lon; vector values(n); GetRangeRangeTree2D rt; rt.init(ys, -INFL); for (int iL = 0, iR = 0; iL != n; ) { for (; iR != n && cities[iR].hei == cities[iL].hei; ++ iR) { const City &c = cities[iR]; int xL = (int)(lower_bound(xis.begin(), xis.end(), make_pair(c.lat - xDiff, -INF)) - xis.begin()); int xR = (int)(upper_bound(xis.begin(), xis.end(), make_pair(c.lat + xDiff, INF)) - xis.begin()); int yL = c.lon - yDiff, yR = c.lon + yDiff + 1; MaxVal sum = rt.getRange(xL, xR, yL, yR); values[iR] = max(0LL, sum.val) + c.pts; } for (; iL != iR; ++ iL) { const City &c = cities[iL]; int xi = (int)(lower_bound(xis.begin(), xis.end(), make_pair(c.lat, iL)) - xis.begin()); rt.set(xi, values[iL]); } } long long ans = 0; rep(i, n) amax(ans, values[i]); printf("%lld\n", ans); } return 0; }