Trees and Decrees

#include <bits/stdc++.h>

using namespace std;

#ifdef NeverBeRed
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ll> point;
#define F first
#define S second



int main()
{
    #ifdef TurnRed
        //freopen("a.in", "r", stdin);
        //freopen("a.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;
    typedef tuple<int, int, int> thr;
    vector<thr> a(m);
    for (auto &i : a)
    {
        int x, y, z;
        cin >> x >> y >> z;
        i = { x, y, z };
    }

    sort(a.begin(), a.end(), [](const thr &x, const thr &y)
    {
        return get<1>(x) < get<1>(y);
    });


    auto f = [&](ll k)
    {
        vector<ll> v(n+2, k);
        vector<int> go(n+2);
        iota(go.begin(), go.end(), 0);

        function<int(int)> run = [&](int x)
        {
            if (v[x] > 0) return x;
            return go[x] = run(go[x+1]);
        };

        for (auto i : a)
        {
            int x, y, z;
            tie(x, y, z) = i;

            for (int g = run(x); g <= y && z > 0; )
            {
                ll t = min((ll)z, v[g]);
                v[g] -= t;
                z -= t;
                if (v[g] == 0)
                    g = run(g+1);
            }

            if (z > 0) return false;
        }

        return true;
    };

    ll l = 0, r = 1e12;
    while (l < r)
    {
        ll md = (l + r) >> 1;
        if (f(md))
            r = md;
        else
            l = md+1;
    }
    cout << l << "\n";

    return 0;
}