POJ 上过不了，复杂度应该是正确的啊

// #pragma GCC optimize(2)
#include <algorithm>
#include <cstdio>
#define int long long
#define max(a,b) ((a > b) ? a : b)
using namespace std;

const int MAXN = 2e4 + 24;
struct Worker
{
    int l,s,p;
    bool operator<(const Worker &a) const {return s < a.s;}
}w[114];
int n,k,dp[114][MAXN];
struct Rukkhadevata{int l,r,val;}tree[MAXN << 2];
void build(int l,int r,int rt,int &val,int a[])
{
    tree[rt].l = l,tree[rt].r = r,tree[rt].val = 0;
    if(l == r)
        return (void)(tree[rt].val = a[l] - val * l);
    int mid = (l + r) >> 1;
    build(l,mid,rt << 1,val,a);
    build(mid + 1,r,rt << 1 | 1,val,a);
    tree[rt].val = max(tree[rt << 1].val,tree[rt << 1 | 1].val);
}
int query(int l,int r,int rt)
{
    if(l <= tree[rt].l && r >= tree[rt].r)
        return tree[rt].val;
    if(r < tree[rt].l || l > tree[rt].r)
        return -0x3f3f3f3f3f3f;
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    return max(query(l,r,rt << 1),query(l,r,rt << 1 | 1));
}
inline void read(int &x)
{
    x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9')
        ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
}
signed main()
{
    read(n),read(k);
    for(int i = 1;i <= k;i++)
        read(w[i].l),read(w[i].p),read(w[i].s);
    sort(w + 1,w + k + 1);
    for(int i(1);i <= k;++i)
    {
        build(0,n,1,w[i].p,dp[i - 1]);
        for(int j(1);j <= n;++j)
        {
            dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
            if(j >= w[i].s)
                dp[i][j] = max(dp[i][j],w[i].p * j + query(j - w[i].l,w[i].s - 1,1));
        }
    }
    printf("%lld\n",dp[k][n]);
    return 0;
}