#include #define endl '\n' using namespace std; const int N = 1<<18; const long long INF = (1e18) + 7; //const long long INF = 0; struct node { int from,to; long long sum; node *left, *right; }; typedef node *node_ptr; node many_nodes[3000000]; int pos; struct dynamic_segment_tree { private: node_ptr root; node_ptr new_node(int l, int r) { node_ptr res=&many_nodes[pos++]; res->from=l; res->to=r; res->sum=-INF; res->left=NULL; res->right=NULL; return res; } void extend(node_ptr &root) { if(root->left==NULL) { root->left=new_node(root->from,(root->from+root->to)>>1); root->right=new_node(((root->from+root->to)>>1)+1,root->to); } } long long sum(node_ptr &a) { if(a==NULL) return -INF; else return a->sum; } void update_tree(node_ptr root, int pos, long long val) { if(root==NULL) return; if(root->from>root->to || root->from>pos || root->tofrom==root->to) { root->sum=max(root->sum,val); return; } extend(root); update_tree(root->left,pos,val); update_tree(root->right,pos,val); root->sum=max(sum(root->left),sum(root->right)); } long long query_tree(node_ptr root, int l, int r) { if(root==NULL) return -INF; if(root->from>root->to || root->from>r || root->tor) return -INF; if(root->from>=l && root->to<=r) return root->sum; extend(root); return max(query_tree(root->left,l,r),query_tree(root->right,l,r)); } public: dynamic_segment_tree() { root=NULL; } void initialize(int n) { if(root==NULL) root=new_node(1,n); } void update(int pos, long long val) { update_tree(root,pos,val); } long long query(int l, int r) { return query_tree(root,l,r); } }; struct city { int x,y,p; city(){} city(int a, int b, int c) { x=a; y=b; p=c; } }; int tests,current_case; int n; vector < city > v[N]; dynamic_segment_tree tree[200000*4 + 17]; long long ans,curr; city a[N]; int x,y; int tmp; void message(int current_case) { //cerr<<"Case "<b || a>pos1 || b>1,pos1,pos2,node<<1,value); update_tree(((a+b)>>1)+1,b,pos1,pos2,(node<<1)|1,value); } long long query_tree(int a, int b, int l1, int r1, int l2, int r2, int node) { if(a>b || a>r1 || b=l1 && b<=r1) { tree[node].initialize(200000); return tree[node].query(l2,r2); } return max(query_tree(a,(a+b)>>1,l1,r1,l2,r2,node<<1),query_tree(((a+b)>>1)+1,b,l1,r1,l2,r2,(node<<1)|1)); } void update(int pos1, int pos2, long long value) { update_tree(1,n,pos1,pos2,1,value); } long long query(int l1, int r1, int l2, int r2) { return query_tree(1,n,l1,r1,l2,r2,1); } int main() { //ios_base::sync_with_stdio(false); //cin.tie(NULL); int i,j; city c; tests=1; //scanf("%d", &tests); //cin>>tests; for(current_case=1;current_case<=tests;current_case++) { scanf("%d %d %d", &n, &x, &y); for(i=1;i<=n;i++) { scanf("%d %d %d %d", &a[i].x, &a[i].y, &tmp, &a[i].p); v[tmp].push_back(a[i]); } for(i=200000;i>=1;i--) { if(v[i].empty()) continue; vector < long long > answers(v[i].size()); for(j=0;j<(int)(v[i].size());j++) { c=v[i][j]; curr=c.p+max(0ll,query(max(1,c.x-x),min(200000,c.x+x),max(1,c.y-y),min(200000,c.y+y))); answers[j]=curr; //printf("Querying { %d, %d }; { %d, %d }: %lld\n", max(1,c.x-x),min(200000,c.x+x),max(1,c.y-y),min(200000,c.y+y), query(max(1,c.x-x),min(200000,c.x+x),max(1,c.y-y),min(200000,c.y+y))); //printf("%lld\n", curr); } for(j=0;j<(int)(v[i].size());j++) { c=v[i][j]; ans=max(ans,answers[j]); update(c.x,c.y,answers[j]); } } printf("%lld\n", ans); MESSAGE: message(current_case); } return 0; }