AtCoder Beginner Contest 017C

C - ハイスコア

0-indexed で考える．
で を表す．

imos法
区間 に対して得点 が対応している．
もしからまでの全ての値を，選んだ区間で覆うと得点は0.
また，0点より大きい得点が欲しければ，一か所でも覆えていなければよい．この場合，選んだ区間のたちの和が得点として入る．
よって，どこで途切れるかを場合分けして全探索．

を途切れさせるとすれば，を含まない区間は全て使うのが最善．
また，
( を覆わない区間全体 ) = ( の区間 ) - (を覆う区間全体)
となるので，たちの和も同様の等式が成り立つ．

( の区間 )のの和は前計算で．
( を覆う区間全体 )のの和はimos 法で．

typedef long long ll;

using vll = vector<long long>;  using vvll = vector<vll>;

#define srep(i,s,t) for (ll i = (s); i < (t); ++i)

#define rep(i,n) srep(i,0,(n))

#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }

int main() {

    ll n, m, k, q;

    cin >> n >> m;

    vll ev(m+10);

    ll t = 0;

    rep(i,n){

        ll l,r,s; cin >> l >> r >> s;

        --l, --r;

        r++;

        ev[l] += s;

        ev[r] -= s;

        t += s;

    }

    vll imos(m+10);

    ll sum = 0;

    rep(i,m+10){

        sum += ev[i];

        imos[i] = sum;

    }

    assert(sum == 0);

    ll ans = 0;

    rep(i,m){

        chmax(ans, t - imos[i]);

    }

    cout << ans << endl;

    return 0;

}