#include #include #include #include #include #include #include #include #include template struct Mapper { int operator[](const T& v) { int& ret = table[v]; if(!ret) rtable[ret = table.size()] = v; return ret - 1; } template int operator()(Args... args) { return (*this)[T(args...)]; } T rev(int idx){return rtable[idx + 1];} std::map table; std::map rtable; }; template struct ReferenceArray { struct It {typename std::array::iterator it; T& operator*(){return **it;} void operator++(){it++;} bool operator!=(const It& other){return it != other.it;} }; int size()const{return _ptr.size();} It begin()const{return {_ptr.begin()};} It end()const{return {_ptr.end()};} T& operator[](int idx)const{return *_ptr[idx];} mutable std::array _ptr; }; template ReferenceArray MAKEV(T& arg1, Args&... args) {return {&arg1, &args...};} struct Range { struct It { int num, step; int operator*(){return num;} void operator++(){num += step;} bool operator!=(const It& other){return num != other.num;} }; Range(int ee):b(0),e(ee){} Range(int bb, int ee):b(bb), e(ee){} It begin(){return {b, (b < e? 1: -1)};} It end(){return {e, 0};} int b, e; }; template inline T& UMAX(T& x, T y){if(x < y)x = y; return x;} template inline T& UMIN(T& x, T y){if(y < x)x = y; return x;} template struct ArithmiticPromotion { typedef decltype(T() + typename ArithmiticPromotion::type()) type; }; template struct ArithmiticPromotion { typedef decltype(T() + U()) type; }; template struct ArithmiticPromotion { typedef T type; }; template struct ArithmiticPromotion { typedef T type; }; template typename ArithmiticPromotion::type MAX(T a, U b) { return a < b? b: a; } template typename ArithmiticPromotion::type MAX(T a, Args... args) { return MAX(a, MAX(args...)); } template typename ArithmiticPromotion::type MIN(T a, U b) { return a < b? a: b; } template typename ArithmiticPromotion::type MIN(T a, Args... args) { return MIN(a, MIN(args...)); } template struct ScanfSpecifier{}; #define DEF(T,V) template<> struct ScanfSpecifier{static constexpr const char* value = V;}; DEF(char*,"%s")DEF(int,"%d")DEF(double,"%lf")DEF(float,"%f")DEF(char,"%c")DEF(const char*,"%s")DEF(unsigned long,"%lu")DEF(unsigned int, "%u") #ifdef _MSC_VER DEF(long long int,"%I64d") #else DEF(long long int,"%lld") #endif #undef DEF template int RD(T& arg){return std::scanf(ScanfSpecifier::value, &arg);} template int RD(char (&arg)[S]){return std::scanf("%s", arg);} int RD(char* arg){return std::scanf("%s", arg);} template<> int RD(char& arg){return std::scanf(" %c", &arg);} template int RD(T& arg1, Args&... args) {return RD(arg1) + RD(args...);} template T RD(){T ret; RD(ret); return ret;} template void RDV(It begin, It end) { while(begin != end) RD(*begin++); } template void RDV(C& c) {RDV(std::begin(c), std::end(c));} template void WT(T arg) {std::printf(ScanfSpecifier::value, arg); } template void WT(std::pair arg) {std::printf("("); WT(arg.first); std::printf(", "); WT(arg.second); std::printf(")");} template void WT(Args... args) { int alc = 0; int dummy[] = {((alc++? std::printf(" "): 0), WT(args), 0)...}; } template void WTL(Args... args) { WT(args...); std::printf("\n"); } template void WTV(It begin, It end) { int alc = 0; while(begin != end) (alc++? std::printf(" "): 0), WT(*begin++); } template void WTV(const C& c) {WTV(std::begin(c), std::end(c));} template void WTVL(It begin, It end) { WTV(begin, end); std::printf("\n"); } template void WTVL(const C& c) {WTVL(std::begin(c), std::end(c));} namespace XX { template class NodeManager, bool Persistent, typename... Infos> class SegmentTree { public: struct NodeData:public T { bool hasLazy = false; }; using PT = typename NodeManager::ParameterType; using Index = typename NodeManager::Index; T& operator[](Index idx) { return _nm[idx]; } Index left(Index idx){return _nm.left(idx);} Index right(Index idx){return _nm.right(idx);} using Modifier = std::function; using Visitor = std::function; Index root(){return _nm.root();} SegmentTree(I beg, I end, Infos&... infos) :_nm(beg, end), _beg(beg), _end(end), _info(infos...) {} Index update(I l, I r, const Modifier& mod) { return update(_nm.root(), l, r, mod); } Index update(Index root, I l, I r, const Modifier& mod) { if(l >= r || r <= _beg || l >= _end) return root; _update(root, _beg, _end, l, r, mod); return root; } T query(I l, I r){return query(_nm.root(), l, r);} T query(Index root, I l, I r) { if(l >= r || r <= _beg || l >= _end) return T(); return _query(root, _beg, _end, l, r); } void queryEach(I l, I r, const Modifier& mod){queryEach(_nm.root(), l, r, mod);} void queryEach(Index root, I l, I r, const Modifier& mod) { if(l >= r || r <= _beg || l >= _end) return; _queryEach(root, _beg, _end, l, r, mod); } Index updateEach(I l, I r, const Modifier& mod){return updateEach(_nm.root(), l, r, mod);} Index updateEach(Index root, I l, I r, const Modifier& mod) { if(l >= r || r <= _beg || l >= _end) return root; _updateEach(root, _beg, _end, l, r, mod); return root; } void travelEach(I l, I r, const Visitor& mod){travelEach(_nm.root(), l, r, mod);} void travelEach(Index root, I l, I r, const Visitor& mod) { if(l >= r || r <= _beg || l >= _end) return; _travelEach(root, _beg, _end, l, r, mod); } void build(const Modifier& mod) { _build(_nm.root(), _beg, _end, mod); } void buildEach(const Modifier& mod) { _buildEach(_nm.root(), _beg, _end, mod); } private: template typename std::enable_if

::type write(Index& idx) { if(!idx->isNull()){auto n = _nm.newnode(); *n = *idx; idx = n;}} template typename std::enable_if

::type write(Index idx) {} void _checkLazy(Index idx, I sl, I sr) { if(_nm[idx].hasLazy) { write(_nm.left(idx)); write(_nm.right(idx)); auto& l = _nm[_nm.left(idx)]; auto& r = _nm[_nm.right(idx)]; I m = (sl + sr) >> 1; l.lazy(sl, m, _nm[idx]); r.lazy(m, sr, _nm[idx]); _nm[idx].clear(); _nm[idx].hasLazy = false; l.hasLazy = r.hasLazy = true; } } template struct Seq{}; template struct GenSeq{using Type = typename GenSeq::Type;}; template struct GenSeq<0, S...>{using Type = Seq;}; template void _update(I l, I m, I r, T& node, T& lc, T& rc, Seq) { node(l, m, r, lc, rc, std::get(_info)...); } void _update(I l, I m, I r, T& node, T& lc, T& rc) { _update(l, m, r, node, lc, rc, typename GenSeq::Type()); } void _buildEach(Index idx, I sl, I sr, const Modifier& mod) { if(sr - sl == 1) mod(sl, sr, _nm[idx]); else { I m = (sl + sr) >> 1; _buildEach(_nm.left(idx), sl, m, mod); _buildEach(_nm.right(idx), m, sr, mod); mod(sl, sr, _nm[idx]); } } void _build(Index idx, I sl, I sr, const Modifier& mod) { if(sr - sl == 1) mod(sl, sr, _nm[idx]); else { I m = (sl + sr) >> 1; _build(_nm.left(idx), sl, m, mod); _build(_nm.right(idx), m, sr, mod); _update(sl, m, sr, _nm[idx], _nm[_nm.left(idx)], _nm[_nm.right(idx)]); } } void _travelEach(Index idx, I sl, I sr, I l, I r, const Visitor& mod) { if(l <= sl && sr <= r) mod(sl, sr, idx); else { _checkLazy(idx, sl, sr); I m = (sl + sr) >> 1; if(l < m) _travelEach(_nm.left(idx), sl, m, l, r, mod); if(r > m) _travelEach(_nm.right(idx), m, sr, l, r, mod); } } void _queryEach(Index idx, I sl, I sr, I l, I r, const Modifier& mod) { if(l <= sl && sr <= r) mod(sl, sr, _nm[idx]); else { _checkLazy(idx, sl, sr); I m = (sl + sr) >> 1; if(l < m) _queryEach(_nm.left(idx), sl, m, l, r, mod); if(r > m) _queryEach(_nm.right(idx), m, sr, l, r, mod); } } T _query(Index idx, I sl, I sr, I l, I r) { if(l <= sl && sr <= r) return _nm[idx]; else { _checkLazy(idx, sl, sr); I m = (sl + sr) >> 1; if(l >= m) return _query(_nm.right(idx), m, sr, l, r); else if(r <= m) return _query(_nm.left(idx), sl, m, l, r); else { T ret; T lt = _query(_nm.left(idx), sl, m, l, m); T rt = _query(_nm.right(idx), m, sr, m, r); _update(l, m, r, ret, lt, rt); return ret; } } } void _updateEach(PT idx, I sl, I sr, I l, I r, const Modifier& mod) { write(idx); if(l <= sl && sr <= r) { mod(sl, sr, _nm[idx]); if(sr - sl > 1) _nm[idx].hasLazy = true; } else { _checkLazy(idx, sl, sr); I m = (sl + sr) >> 1; if(l < m) _updateEach(_nm.left(idx), sl, m, l, r, mod); if(r > m) _updateEach(_nm.right(idx), m, sr, l, r, mod); mod(sl, sl, _nm[idx]); } } void _update(PT idx, I sl, I sr, I l, I r, const Modifier& mod) { write(idx); if(l <= sl && sr <= r) { mod(sl, sr, _nm[idx]); if(sr - sl > 1) _nm[idx].hasLazy = true; } else { _checkLazy(idx, sl, sr); I m = (sl + sr) >> 1; if(l < m) _update(_nm.left(idx), sl, m, l, r, mod); if(r > m) _update(_nm.right(idx), m, sr, l, r, mod); _update(sl, m, sr, _nm[idx], _nm[_nm.left(idx)], _nm[_nm.right(idx)]); } } std::tuple _info; NodeManager _nm; I _beg, _end; }; } namespace XX { template class MemoryManager { public: static constexpr const int INIT = INITBUF / BLOCKSIZE; static MemoryManager* inst() { static MemoryManager ret; return &ret; } void* alloc() { void* ret; if(_ptr) { ret = _ptr; _ptr = *static_cast(_ptr); } else { if(_pos == _size) { _pos = 0; _buf[++_idx] = new char[std::max(_size <<= 1, 1)]; } ret = _buf[_idx] + _pos; _pos += BLOCKSIZE; } return ret; } void dealloc(void* p) { *static_cast(p) = _ptr; _ptr = p; } ~MemoryManager() { for(int i = 1; i <= _idx; i++) delete []_buf[i]; } private: MemoryManager() { _buf[0] = _init; } char _init[INIT * BLOCKSIZE]; int _size = INIT * BLOCKSIZE; int _idx = 0; int _pos = 0; char* _buf[32] = {}; void* _ptr = nullptr; }; template struct BlockAllocater { void* operator new(std::size_t count) { return MemoryManager::inst()->alloc(); } void operator delete(void* ptr) { return MemoryManager::inst()->dealloc(ptr); } }; template struct NullNode { static T nullnode; static T* null() { return &nullnode; } bool isNull(){return this == null();} }; template T NullNode::nullnode; } namespace XX { template class DynamicTreeNodeManager { public: struct Node:public T, BlockAllocater, NullNode { Node* left = this->null(); Node* right = this->null(); }; typedef Node* Index; typedef Index& ParameterType; private: Node* _root = newnode(); public: DynamicTreeNodeManager(int beg, int end){ } Index root(){return _root;} Node* newnode() { return new Node(); } Index& left(Index idx) { if(idx->left->isNull()) idx->left = newnode(); return idx->left; } Index& right(Index idx) { if(idx->right->isNull()) idx->right = newnode(); return idx->right; } Node& operator[](Index idx) {return *idx;} }; } namespace XX { template using DynamicSegmentTree = XX::SegmentTree; } template class LazyPtr { public: template T& operator()(Args... args) { if(!init)new (_buf)T(args...); init = true; return **this;} T* operator->() { return ((T*)_buf); } T& operator*() { return *((T*)_buf); } private: bool init = false; char _buf[sizeof(T)]; }; //alias //SegmentTree //Modifier void(int l, int r, T&) //update(int l, int r, Modifier mod) //query(int l, int r) //SegmentTree data typedef long long int ll; //RD[L],RDV[L],WT[L],WTV[L] for i/o //DynamicSegmentTree using XX::DynamicSegmentTree; using RG = Range; //template #include #include #include #include #include #include #include #include using namespace std; struct DataY { ll mx = 0; void clear(){} void lazy(int sl, int sr, DataY& up){} void operator()(int l, int m, int r, DataY& lc, DataY& rc) { mx = MAX(0, lc.mx, rc.mx); } }; struct DataX { LazyPtr> sgty; void clear(){} void lazy(int sl, int sr, DataX& up){} void operator()(int l, int m, int r, DataX& lc, DataX& rc){} }; const int SIZE = 200009; struct City { int x, y, h, p; bool operator<(const City& rhs)const { return h < rhs.h; } }cs[SIZE]; ll ans[SIZE]; int main() { int N, X, Y; RD(N, X, Y); DynamicSegmentTree sgtx(0, SIZE); for(int i: RG(N)) RD(cs[i].x, cs[i].y, cs[i].h, cs[i].p); sort(cs, cs + N); ll ans = 0; for(int i: RG(N)) { ll v = 0; sgtx.queryEach(max(cs[i].x - X, 0), min(cs[i].x + X + 1, SIZE), [&](int sl, int sr, DataX& data) { UMAX(v, data.sgty(0, SIZE).query(max(cs[i].y - Y, 0), min(cs[i].y + Y + 1, SIZE)).mx); }); v += cs[i].p; UMAX(ans, v); if(v > 0) sgtx.updateEach(cs[i].x, cs[i].x + 1, [&](int, int, DataX& data) { data.sgty(0, SIZE).update(cs[i].y, cs[i].y + 1, [&](int, int, DataY& data) { UMAX(data.mx, v); }); }); } WTL(ans); }