#include using namespace std; #define ll long long #define ull unsigned long long #define ld long double using LL = long long; using ULL = unsigned long long; using VI = vector; using VVI = vector; using VVVI = vector; using VL = vector; using VVL = vector; using VVVL = vector; using VB = vector; using VVB = vector; using VVVB = vector; using VD = vector; using VVD = vector; using VVVD = vector; using VC = vector; using VS = vector; using VVC = vector; using PII = pair; using PLL = pair; using PDD = pair; using PIL = pair; using MII = map; using MLL = map; using SI = set; using SL = set; using MSI = multiset; using MSL = multiset; template using MAXPQ = priority_queue; template using MINPQ = priority_queue< T, vector, greater >; const ll MOD = 1000000007; const ll MOD2 = 998244353; const ll INF = 1LL << 60; #define PI 3.14159265358979323846 #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define REP(i, n) FOR(i, 0, n) #define EACH(e, v) for(auto &e : v) #define RITR(it, v) for(auto it = (v).rbegin(); it != (v).rend(); ++it) #define ALL(v) v.begin(),v.end() vector x8={1,1,1,0,0,-1,-1,-1},y8={1,0,-1,1,-1,1,0,-1}; int dx4[4]={1,-1,0,0}, dy4[4]={0,0,1,-1}; /* memo -uf,RMQ(segtree),BIT,BIT2,SegTree,SegTreeLazy -isprime,Eratosthenes,gcdlcm,factorize,divisors,modpow,moddiv nCr(+modnCr,inverse,extend_euclid.powmod),tobaseB,tobase10 -dijkstra,Floyd,bellmanford,sccd,topological,treediamiter -compress1,compress2,rotate90 -co,ci,fo1,fo2,fo3,fo4 -bitsearch,binaryserach -bfs -SegTreedec,SegTreeLazydec */ template struct LazySegTree{ using FX = function; using FA = function; using FM = function; long long n, N, log; vector dat; vector lazy; FX fx; FA fa; FM fm; X ex; M em; LazySegTree(long long _n, FX _fx, FA _fa, FM _fm, X _ex, M _em){ init(_n,_fx,_fa,_fm,_ex,_em); } void init(long long _n, FX _fx, FA _fa, FM _fm, X _ex, M _em){ N = _n, fx = _fx, fa = _fa, fm = _fm, ex = _ex, em = _em; long long x = 1; log = 0; while(_n > x) x *= 2, log++; n = x; dat.assign(n*2,ex); lazy.assign(n*2,em); } void pull_dat(long long k){ dat[k] = fx(dat[2*k],dat[2*k+1]); } void apply_lazy(long long k, M f){ dat[k] = fa(f, dat[k]); if(k < n) lazy[k] = fm(f, lazy[k]); } void push_lazy(long long k){ if(lazy[k] == em) return; apply_lazy(2*k, lazy[k]); apply_lazy(2*k + 1, lazy[k]); lazy[k] = em; } void pull_dat_deep(long long k){ for(int h = 1; h <= log; h++) pull_dat(k >> h); } void push_lazy_deep(long long k){ for(int h = log; h >= 1; h--) push_lazy(k >> h); } //i番目の要素をxにアップデートする(0-indexed),O(logN) void set(long long i, X x){ i += n; push_lazy_deep(i); dat[i] = x; pull_dat_deep(i); } //i番目の要素にアクセス(0-indexed),O(logN); X get(long long i){ i += n; push_lazy_deep(i); return dat[i]; } X operator[](long long i){return get(i);}; //i番目の要素にfaを作用させる void apply(long long i, M f){ i += n; push_lazy_deep(i); dat[i] = fa(f, dat[i]); pull_dat_deep(i); } //[l,r)までfaを作用させる void apply(long long l, long long r, M f){ if(l == r) return; l += n, r += n; for(int h = log; h >= 1; h--){ if(((l >> h) << h) != l) push_lazy(l >> h); if(((r >> h) << h) != r) push_lazy((r-1) >> h); } long long L = l, R = r; for(;l < r; l >>= 1, r >>= 1){ if(l & 1) apply_lazy(l++,f); if(r & 1) apply_lazy(--r,f); } l = L, r = R; for(int h = 1; h <= log; h++){ if(((l >> h) << h) != l) pull_dat(l >> h); if(((r >> h) << h) != r) pull_dat((r-1) >> h); } } //[l,r)で二項演算を作用した結果(0-indexed),O(logN) X prod(long long l, long long r){ if(l == r) return ex; l += n, r += n; for(int h = log; h >= 1; h--){ if(((l >> h) << h) != l) push_lazy(l >> h); if(((r >> h) << h) != r) push_lazy(r >> h); } X vleft = ex, vright = ex; for(; l < r; l >>= 1, r >>= 1){ if(l & 1) vleft = fx(vleft,dat[l++]); if(r & 1) vright = fx(dat[--r],vright); } return fx(vleft,vright); } X all_prod(){return dat[1];}; //x=prod(l,r),f(x)=trueとなる最大のrを求める(f(ex)=true, 0-indexed),O(logN) long long max_right(function f, long long l = 0){ if(l == N) return N; l += n; push_lazy_deep(l); X sum = ex; do{ while(l % 2 == 0) l >>= 1; if(!f(fx(sum,dat[l]))){ while(l < n){ push_lazy(l); l *= 2; if(f(fx(sum,dat[l]))){ sum = fx(sum,dat[l]); l++; } } return l - n; } sum = fx(sum,dat[l]); l++; }while((l & -l) != l); return N; } //x=prod(l,r),f(x)=trueとなる最小のlを求める(f(ex)=true, 0-indexed),O(logN) long long min_left(function f, long long r = -1){ if(r == 0) return 0; if(r == -1) return N; r += n; push_lazy_deep(r-1); X sum = ex; do{ r--; while(r > 1 && (r % 2)) r >>= 1; if(!f(fx(dat[r],sum))){ while(r < n){ push_lazy(r); r *= 2; if(f(fx(dat[r],sum))){ sum = fx(dat[r],sum); r--; } } return r + 1 - n; } sum = fx(dat[r],sum); }while((r & -r) != r); return 0; } }; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); ll N,T; cin >> N >> T; VL l(N),r(N),p(N); for(ll i = 0; i < N; i++) cin >> l[i] >> r[i] >> p[i]; vector h; for(ll i = 0; i < N; i++) h.push_back({p[i],i}); sort(ALL(h)); ll K = 2e5; using X = ll; using M = ll; auto fx = [](X x1, X x2){return min(x1,x2);}; X ex = -1; M em = -INF; auto fa = [](M m, X x){return (m != -INF? m : x);}; auto fm = [](M m1, M m2){return (m1 != -INF? m1 : m2 );}; LazySegTree point(K+1,fx,fa,fm,ex,em); for(ll i = 0; i < N; i++){ auto [P,id] = h[i]; ll L = l[id],R = r[id]; point.apply(L,R+1,P); } VL dp(K+2,0); for(ll i = 0; i <= K; i++){ ll P = point[i]; ll nxt = min(K+1,i+T); dp[i+1] = max(dp[i+1],dp[i]); dp[nxt] = max(dp[nxt],dp[i]+P); } cout << dp[K+1] << '\n'; }