题意:n 个墙壁 m 个粉刷匠，每个墙壁至多能被刷一次，每个粉刷匠要么不刷，要么就粉刷包含第 Si 块的长度不超过 Li 的连续墙壁 (中间可不刷),每一块被刷的墙壁都可获得 Pi 的利润，求最大利润

避免重复粉刷：

首先对 Si 排序并定义 \(f[i][j]\)：前 i 个木匠处理到第 j 块木板时的最大利润

此时[j+1,n]保证没被处理以满足无后效性

保证情况一的合法

\[f[i][j]=f[i-1][j]\]

保证情况二的 Si 必须被粉刷

定义处理的区间为[k+1,j]

则 \(f[i][j]=max_kf[i-1][k]+P_i*(j-k)\)

此时要求 Si 必须在[k+1,j]内部，则对 k 加以限定：\(k+1≤S_i≤j\)

连续长度的表示：\(j-k≤L_i\)

中间可空出部分的表示 \(f[i][j]=f[i][j-1]\)

由此可总结转移方程的三部分

前两部分为 \(f[i][j]=max(f[i-1][j],f[i][j-1])\)

最后一部分为 \(f[i][j]=max_{j-L_i≤k≤S_i-1}f[i-1][k]+P_i*(j-k),S_i≤j\)

对于第三部分可改写方程为 \(f[i][j]=max_{j-L_i≤k≤S_i-1}(f[i-1][k]-k*P_i)+j*P_i,S_i≤j\) 以满足单调队列优化

单调队列在 \(i\) 的内循环当中可认为 \(i\) 是常数，也就是说每一层 \(i\) 都需要设立一个只与 \(k\) 有关的单调队列 \(que\)，但在实际中只使用一个

\(que\) 每一次的初始化范围由最小的 \(j\) 决定 由 \(S_i≤j\)和\(j-L_i≤k≤S_i-1\)

得 \(S_i-L_i≤k_{init}≤S_i-1\)

此时 \(j=1\) 则得到所有有效的状态 \(k\)

更新过程保证头部 \(val\) 最优，\(k\) 单调递增 (因为后者的更新顺序是从左往右)

注意单调更新时只对头部更新，因为单调范围右边界总是 \(S_i-1\)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iter(i,j) for(int i=0;i<(j).size();i++)
#define print(a) printf("%lld",(ll)a)
#define println(a) printf("%lld\n",(ll)a)
#define printbk(a) printf("%lld ",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int MAXN = 2e4+11;
const int oo = 0x3f3f3f3f;
typedef long long ll;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct XJB{
    int l,p,s;
    bool operator < (const XJB &r) const{
        return s<r.s;
    }
}a[MAXN];
int n,m;
int f[233][MAXN];
inline int cal(int i,int k){
    return f[i-1][k]-a[i].p*k;
}
int main(){
    while(cin>>n>>m){
        rep(i,1,m){
            a[i].l=read();
            a[i].p=read();
            a[i].s=read();
        }
        sort(a+1,a+1+m);
        memset(f,0,sizeof f);
        deque<int> que;
        rep(i,1,m){
            while(!que.empty()) que.pop_back();
            rep(k,max(0,a[i].s-a[i].l),a[i].s-1){ //j-Li<=k<=Si-1,j>=Si
                while(!que.empty()&&cal(i,k)>=cal(i,que.back())) que.pop_back();
                que.push_back(k);
            }
            rep(j,1,n){
                f[i][j]=max(f[i-1][j],f[i][j-1]);
                if(j>=a[i].s){
                    while(!que.empty()&&que.front()<j-a[i].l) que.pop_front();
                    if(!que.empty()) f[i][j]=max(f[i][j],cal(i,que.front())+a[i].p*j);
                }
            }
        }
        println(f[m][n]);
    }
    return 0;
}