#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using pii = pair; using pll = pair; template using vc = vector; template using vvc = vector>; template using vvvc = vector>>; template using pq = priority_queue,greater>; template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } int dx4[] = {1,0,-1,0}; int dy4[] = {0,1,0,-1}; #define overload5(a, b, c, d, e, name, ...) name #define overload4(a, b, c, d, name, ...) name #define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf) #define REP1(i, n) for(ll i = 0; i < (n); ++i) #define REP2(i, a, b) for(ll i = (a); i < (b); ++i) #define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c)) #define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__) #define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf) #define per1(i, n) for(ll i = (n)-1; i >= 0; --i) #define per2(i, a, b) for(ll i = (a)-1; i >= b; --i) #define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c)) #define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__) #define setbits(j, n) for(ll iiiii = (n), j = lowbit(iiiii); iiiii; iiiii ^= 1 << j, j = lowbit(iiiii)) #define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(all(v)));) #define fi first #define se second #define pb push_back #define ppb pop_back #define ppf pop_front #define drop(s) cout << #s << endl, exit(0) #define si(c) (int)(c).size() #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{})) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{})) #define rng(v, l, r) v.begin() + (l), v.begin() + (r) #define all(c) c.begin(), c.end() #define rall(c) c.rbegin(), c.rend() #define SORT(v) sort(all(v)) #define REV(v) reverse(all(v)) #define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end()) #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define overload2(_1, _2, name, ...) name #define vec(type, name, ...) vector name(__VA_ARGS__) #define vv(type, name, h, ...) vector> name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) vector>> name(h, vector>(w, vector(__VA_ARGS__))) ll inf = 1001001001001001001; template struct LazySegmentTree { int n; vector dat; vectorlazy; LazySegmentTree() {}; LazySegmentTree(int N) { n = 1; while(n < N) { n *= 2; } dat.resize(n*2,0); lazy.resize(n*2,0); } void eval(int k,int l,int r) { if(lazy[k] == 0) return; if(k < n) { lazy[k*2] += lazy[k]; lazy[k*2+1] += lazy[k]; } dat[k] += lazy[k]; lazy[k] = 0; } void update(int a, int b, T x, int k, int l, int r) { eval(k,l,r); if(a <= l && r <= b) { lazy[k] += x; eval(k,l,r); } else if(a < r && l < b) { update(a, b, x, k*2, l, (l+r)/2); update(a, b, x, k*2+1, (l+r)/2, r); dat[k] = max(dat[k*2],dat[k*2+1]); } } void update(int a, int b, T x) {//[a,b) update(a, b, x, 1, 0, n); } T query_sub(int a, int b, int k, int l, int r) { eval(k,l,r); if (r <= a || b <= l) { return -inf; } else if (a <= l && r <= b) { return dat[k]; } else { T vl = query_sub(a, b, k*2, l, (l+r)/2); T vr = query_sub(a, b, k*2+1, (l+r)/2, r); return max(vl,vr); } } T query(int a, int b) {//[a,b) return query_sub(a, b, 1, 0, n); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,s,h; cin >> n >> s >> h; vcx(n),y(n),z(n),cmp; rep(i,n) { cin >> x[i] >> y[i] >> z[i]; cmp.pb(x[i]); cmp.pb(y[i]); } cmp.pb(2002002002); UNIQUE(cmp); LazySegmentTreeSeg(si(cmp)); vvctmp(si(cmp)); rep(i,n) { int it1 = lower_bound(all(cmp),x[i])-cmp.begin(); int it2 = lower_bound(all(cmp),y[i])-cmp.begin(); tmp[it2].pb({it1,z[i]}); } ll ans = 0; vcdp(si(cmp)); rep(i,si(cmp)-1) { for(auto j:tmp[i]) { Seg.update(0,j.fi+1,j.se); } int it = lower_bound(all(cmp),cmp[i]-s)-cmp.begin(); ll mx = Seg.query(it,i+1); chmax(ans,mx); int nxt = lower_bound(all(cmp),cmp[i]+h)-cmp.begin(); chmax(dp[nxt],mx); chmax(dp[i+1],dp[i]); Seg.update(i,i+1,dp[i]); } cout << ans << "\n"; }