先把所有工匠按照Si排序，这样一来，每个工匠粉刷的木板一定在上一个工匠粉刷的木板之后，使我们能够按照顺序进行线性DP
设F[i,j]表示安排前i个工匠粉刷前j块木板（可以有空着不刷的木板），工匠们能获得的最多报酬。
1. 第i个工匠可以什么也不刷，此时F[i,j]=F[i-1,j]
2. 第j块木板可以空着不刷，此时F[i,j]=F[i,j-1]
3. 第i个工匠粉刷第k+1块到第j块木板。根据题意，该工匠粉刷总数不能超过Li，且必须粉刷Si，所以
需要满足：k+1≤Si≤j并且j-k≤Li。于是，$S_i\leq j$时有状态转移方程：
$F[i,j]=\max_{j-L_i\leq k\leq S_i-1}(F[i-1,k]+P_i\times(j-k))$

复杂度$O(n^2)$
我们重点来看这个状态转移方程的优化。首先，我们多次提到，在考虑内层循环j以及决策k时，可以把
外层循环变量i看作定值。这样一来，状态转移方程中的各项可分为两部分：

• Pi×j，除了定值i之外，只有状态变量j
• F[i-1,k]-Pi×k，除定值i外，只有决策变量k。

状态转移方程可以改写为：$S_i\leq j$时
① $F[i,j]=P_i\times j+\max_{j-L_i\leq k\leq S_i-1}(F[i-1,k]-P_i\times k)$

当j增大时，k的取值范围上界Si-1不变，下界j-Si变大。
则用单调队列维护最大值即可。
具体地，在i不变的一层循环前，先将①式中max部分$O(n)$存入单调队列。
每次决策while判断一下队首是否满足$j-L_i\leq k\leq S_i-1$即可（不满足pop）
CODE:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mkp make_pair
#define G pair<int,pair<int,int> >
#define S first
#define L second.first
#define P second.second
#define FOR(i,j,k) for(register int i=j;(j<k)?(i<=k):(i>=k);i+=(j<k)?1:(-1))
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define N 16100 
#define M 110 
inline void ckmx(int &a,int b){
    a=max(a,b); 
}
deque<pair<int,int> > q;
G g[M];
int n,m;
int dp[M][N];
void push(pair<int,int> x){
    while(!q.empty() && q.back().first<=x.first)q.pop_back();
    q.push_back(x);
}
signed main(){
    IO;
    cin>>n>>m;
    FOR(i,1,m)cin>>g[i].L>>g[i].P>>g[i].S;
    sort(g+1,g+1+m);
//    FOR(i,1,m)cout<<g[i].L<<" "<<g[i].P<<" "<<g[i].S<<endl;
    FOR(j,1,n)dp[0][j]=0;
    FOR(i,1,m){
        q.clear();
        FOR(j,max(0,g[i].S-g[i].L),g[i].S-1)push(mkp(dp[i-1][j]-g[i].P*j,j));
//      cout<<q.front().first<<" "<<q.front().second<<endl;
        FOR(j,1,n){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(j>=g[i].S){
                while(!q.empty() && q.front().second<j-g[i].L)q.pop_front();
                if(!q.empty()) ckmx(dp[i][j],g[i].P*j+q.front().first);
//              cout<<i<<" "<<j<<" "<<g[i].P*j<<" "<<q.front().first<<endl;
            }
        }
    }
//  FOR(i,1,m){
//      FOR(j,1,n){
//          cout<<dp[i][j]<<" ";
//      }
//      cout<<endl;
//  }
    cout<<dp[m][n]<<endl;
    return 0;
}

码字不易，但求兹磁