/* -*- coding: utf-8 -*- * * 3424.cc: No.3424 Shooting Game - yukicoder */ #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 200000; const int MAX_R = 200000 + 2; /* typedef */ using ll = long long; using vi = vector; using msig = multiset>; /* global variables */ vi lps[MAX_R], rps[MAX_R]; ll dp[MAX_R]; /* subroutines */ void setmax(ll &a, ll b) { if (a < b) a = b; } /* main */ int main() { int n, t; scanf("%d%d", &n, &t); int maxr = 0; for (int i = 0; i < n; i++) { int l, r, p; scanf("%d%d%d", &l, &r, &p); lps[l].push_back(p); rps[r].push_back(p); maxr = max(maxr, r); } msig ps; fill(dp, dp + maxr + 2, -1); dp[0] = 0; for (int i = 0; i <= maxr; i++) { setmax(dp[i + 1], dp[i]); for (auto p: lps[i]) ps.insert(p); if (! ps.empty()) setmax(dp[min(maxr + 1, i + t)], dp[i] + *ps.begin()); for (auto p: rps[i]) ps.erase(ps.find(p)); } printf("%lld\n", dp[maxr + 1]); return 0; }