#include using namespace std; using ll = long long; const int INF = (int)1e9 + 1001010; const ll llINF = (long long)4e18 + 22000020; const string endn = "\n"; template inline auto vector2(size_t i, size_t j, const T &init = T()) {return vector(i, vector(j, init));} const string ELM_SEP = " ", VEC_SEP = endn; template istream& operator >>(istream &i, vector &A) {for(auto &I : A) {i >> I;} return i;} template ostream& operator <<(ostream &o, const vector &A) {int i=A.size(); for(const auto &I : A){o << I << (--i ? ELM_SEP : "");} return o;} template ostream& operator <<(ostream &o, const vector> &A) {int i=A.size(); for(const auto &I : A){o << I << (--i ? VEC_SEP : "");} return o;} template vector& operator ++(vector &A, int n) {for(auto &I : A) {I++;} return A;} template vector& operator --(vector &A, int n) {for(auto &I : A) {I--;} return A;} template bool chmax(T &a, const U &b) {return ((a < b) ? (a = b, true) : false);} template bool chmin(T &a, const U &b) {return ((a > b) ? (a = b, true) : false);} ll floor(ll a, ll b){if (b < 0) a = -a, b = -b; if(a >= 0) return a / b; else return (a + 1) / b - 1;} ll ceil(ll a, ll b){if (b < 0) a = -a, b = -b; if(a > 0) return (a - 1) / b + 1; else return a / b;} ll bit(unsigned long long val, unsigned long long digit){return (val >> digit) & 1;} #ifdef DEBUG #include #define dump(...) cpp_dump(__VA_ARGS__) namespace cp = cpp_dump; struct InitCppDump{ InitCppDump(){ if(!isatty(fileno(stderr))) CPP_DUMP_SET_OPTION(es_style, cpp_dump::es_style_t::no_es); CPP_DUMP_SET_OPTION(log_label_func, cp::log_label::line()); CPP_DUMP_SET_OPTION(max_iteration_count, 30); } } init_cpp_dump; #else #define dump(...) #endif // ================================== ここまでテンプレ ================================== // ACLの実装を一部改変したもの // == 変更点 == // internal::ceil_pow2 を埋め込み // add関数 を追加 // size関数 を追加 template struct segtree { public: segtree() : segtree(0) {} explicit segtree(int n) : segtree(vector(n, e())) {} explicit segtree(const vector& v) : _n(int(v.size())) { log = 0; while((1U << log) < (unsigned int)(_n)) log++; _size = 1 << log; d = vector(2 * _size, e()); for (int i = 0; i < _n; i++) d[_size + i] = v[i]; for (int i = _size - 1; i >= 1; i--) { update(i); } } size_t size() const { return _n; } void set(int p, S x) { assert(0 <= p && p < _n); p += _size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } void add(int p, S x){ assert(0 <= p && p < _n); p += _size; d[p] += x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) const { assert(0 <= p && p < _n); return d[p + _size]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += _size; r += _size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return d[1]; } template int max_right(int l) const { return max_right(l, [](S x) { return f(x); }); } template int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += _size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < _size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - _size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) const { return min_left(r, [](S x) { return f(x); }); } template int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += _size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < _size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - _size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } friend ostream& operator<<(ostream &os, const segtree &st) { os << "["; for (int i = 0; i < st._n; i++) { if (i != 0) os << ", "; os << st.get(i); } os << "]"; return os; } private: int _n, _size, log; vector d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; template struct RangeSum { static S op(S l, S r){ return l + r; } static S e(){ return 0; } using Type = struct segtree; }; template struct RangeMin { static S op(S l, S r){ return min(l, r); } static S e(){ return numeric_limits::max(); } using Type = struct segtree; }; template struct RangeMax { static S op(S l, S r){ return max(l, r); } static S e(){ return numeric_limits::min(); } using Type = struct segtree; }; // ex) RangeMin::Type seg(10); template ll binary_search_ll(ll ok, ll ng, Judgement judge){ auto need_continue = [&]() -> bool { if(ok > ng) return((__int128_t)ok - (__int128_t)ng > 1); else return ((__int128_t)ng - (__int128_t)ok > 1); }; while(need_continue()){ ll mid = ((__int128_t)ok + (__int128_t)ng) / 2; if(judge(mid)) ok = mid; else ng = mid; } return ok; }; int main(int argc, char *argv[]){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n, s, h; cin >> n >> s >> h; vector x, y, z; for(int i = 0; i < n; i++){ ll tx, ty, tz; cin >> tx >> ty >> tz; ll len = ty - tx; if(len <= s){ x.push_back(tx); y.push_back(ty); z.push_back(tz); } } n = x.size(); dump(x); dump(y); dump(z); vector cz(n+1, 0); for(int i = 0; i < z.size(); i++) cz[i+1] = cz[i] + z[i]; RangeMax::Type dp_s(vector(n+1, 0)); dp_s.set(0, cz[n]); ll ans = 0; for(int i = 0; i < n; i++){ // i番目の授業の終わりと同時に寝る { ll from = ranges::lower_bound(x, y[i] - s) - x.begin(); ll max_val = dp_s.prod(from, i+1); ll this_ans = max_val - (cz[n] - cz[i+1]); chmax(ans, this_ans); ll to = ranges::lower_bound(x, y[i] + h) - x.begin(); dp_s.set(to, max(dp_s.get(to), max_val - (cz[to] - cz[i+1]))); dump(i, x[i], y[i], from, to, max_val, this_ans); } // i番目の授業を受けない if(i+1 < n){ dp_s.set(i+1, max(dp_s.get(i+1), dp_s.get(i) - z[i])); } dump(dp_s); } cout << ans << endl; return 0; }