//start of jonathanirvings' template v3.0.3 (BETA) #include using namespace std; typedef long long LL; typedef pair pii; typedef pair pll; typedef pair pss; typedef vector vi; typedef vector vvi; typedef vector vii; typedef vector vl; typedef vector vvl; double EPS = 1e-9; int INF = 1000000005; long long INFF = 1000000000000000005LL; double PI = acos(-1); int dirx[8] = {-1,0,0,1,-1,-1,1,1}; int diry[8] = {0,1,-1,0,-1,1,-1,1}; #ifdef TESTING #define DEBUG fprintf(stderr,"====TESTING====\n") #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define DEBUG #define VALUE(x) #define debug(...) #endif #define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a)) #define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a)) #define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a)) #define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a)) #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) #define FOREACH(a,b) for (auto &(a) : (b)) #define REP(i,n) FOR(i,0,n) #define REPN(i,n) FORN(i,1,n) #define MAX(a,b) a = max(a,b) #define MIN(a,b) a = min(a,b) #define SQR(x) ((LL)(x) * (x)) #define RESET(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define mp make_pair #define pb push_back #define ALL(v) v.begin(),v.end() #define ALLA(arr,sz) arr,arr+sz #define SIZE(v) (int)v.size() #define SORT(v) sort(ALL(v)) #define REVERSE(v) reverse(ALL(v)) #define SORTA(arr,sz) sort(ALLA(arr,sz)) #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) #define PERMUTE next_permutation #define TC(t) while(t--) inline string IntToString(LL a){ char x[100]; sprintf(x,"%lld",a); string s = x; return s; } inline LL StringToInt(string a){ char x[100]; LL res; strcpy(x,a.c_str()); sscanf(x,"%lld",&res); return res; } inline string GetString(void){ char x[1000005]; scanf("%s",x); string s = x; return s; } inline string uppercase(string s){ int n = SIZE(s); REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A'; return s; } inline string lowercase(string s){ int n = SIZE(s); REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a'; return s; } inline void OPEN (string s) { #ifndef TESTING freopen ((s + ".in").c_str (), "r", stdin); freopen ((s + ".out").c_str (), "w", stdout); #endif } //end of jonathanirvings' template v3.0.3 (BETA) int n,x,y; pair data[200005]; pii P[200005]; int p[200005]; vector pos[800005]; vector val[800005]; int sz[800005]; void preassign(int ix,int L,int R,int x) { ++sz[ix]; if (L == R) return; int M = (L + R) >> 1; if (x <= M) preassign(ix*2+1,L,M,x); else preassign(ix*2+2,M+1,R,x); } void assign(int ix,int L,int R,int x,int y) { // pos[ix].pb(y); --sz[ix]; pos[ix][sz[ix]] = y; if (L == R) return; int M = (L + R) >> 1; if (x <= M) assign(ix*2+1,L,M,x,y); else assign(ix*2+2,M+1,R,x,y); } inline void update1D(int ix1,int ix2,int L,int R,int y,LL v) { // debug("<<<<<<%d %d %d %d %d %lld\n",ix1,ix2,L,R,y,v); MAX(val[ix1][ix2],v); if (L == R) return; int M = (L + R) >> 1; if (y <= pos[ix1][M]) update1D(ix1,ix2*2+1,L,M,y,v); else update1D(ix1,ix2*2+2,M+1,R,y,v); } inline void update2D(int ix,int L,int R,int x,int y,LL v) { // debug("<<%d %d %d %d %d %lld\n",ix,L,R,x,y,v); // int temp = lower_bound(ALL(pos[ix]),y) - pos[ix].begin(); update1D(ix,0,0,SIZE(pos[ix])-1,y,v); if (L == R) return; int M = (L + R) >> 1; if (x <= M) update2D(ix*2+1,L,M,x,y,v); else update2D(ix*2+2,M+1,R,x,y,v); } inline LL query1D(int ix1,int ix2,int L,int R,int ya,int yb) { // debug(">>>>>%d %d %d %d %d %d\n",ix1,ix2,L,R,ya,yb); if (ya <= pos[ix1][L] && pos[ix1][R] <= yb) return val[ix1][ix2]; if (pos[ix1][R] < ya || yb < pos[ix1][L]) return 0; int M = (L + R) >> 1; return max(query1D(ix1,ix2*2+1,L,M,ya,yb),query1D(ix1,ix2*2+2,M+1,R,ya,yb)); } inline LL query2D(int ix,int L,int R,int xa,int xb,int ya,int yb) { // debug(">>%d %d %d %d %d %d %d\n",ix,L,R,xa,xb,ya,yb); if (xa <= L && R <= xb) { if (pos[ix].empty()) return 0; // if (tempa > tempb) return 0; return query1D(ix,0,0,SIZE(pos[ix])-1,ya,yb); } if (R < xa || xb < L) return 0; int M = (L + R) >> 1; return max(query2D(ix*2+1,L,M,xa,xb,ya,yb),query2D(ix*2+2,M+1,R,xa,xb,ya,yb)); } bool f(pair a, pair b) { return a.se.se > b.se.se; } int main() { scanf("%d %d %d",&n,&x,&y); REP(i,n) { scanf("%d %d %d %d",&data[i].se.fi,&data[i].se.se,&data[i].fi.fi,&data[i].fi.se); } sort(ALLA(data,n),f); REP(i,n) preassign(0,0,200000,data[i].se.fi); FORN(i,0,800000) { // SORT(pos[i]); pos[i].resize(sz[i]); val[i].resize(sz[i]*4); } REP(i,n) assign(0,0,200000,data[i].se.fi,data[i].se.se); SORTA(data,n); REP(i,n) { P[i] = data[i].se; p[i] = data[i].fi.se; } // REP(i,n) assign(0,0,200000,P[i].fi,P[i].se); // FORN(i,0,800000) // { // // SORT(pos[i]); // val[i].resize(SIZE(pos[i])*4); // } LL risan = 0; // return 0; FORD(i,n-1,0) { // VALUE(i); int xa = max(0,P[i].fi-x); int xb = min(200000,P[i].fi+x); int ya = max(0,P[i].se-y); int yb = min(200000,P[i].se+y); LL temp = query2D(0,0,200000,xa,xb,ya,yb); // VALUE(temp); temp += p[i]; MAX(risan,temp); update2D(0,0,200000,P[i].fi,P[i].se,temp); } printf("%lld\n",risan); return 0; }