把工匠按照$S_i$排序之后，那么每个工匠的刷的木板一定在前一个工匠之后，因此可以进行线性DP。

$f_{i,j}=\begin{cases}f_{i-1,j}\\f_{i,j-1}\\\max\limits_{s_i-l_i-1\le k< s_i}f_{i-1,k}+c_i*(j-k)\end{cases}$

发现可以滚掉第一维，之后就不用前面两个状态了。

之后单调队列即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=105;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int s,p,l;bool operator <(const node a)const{return s<a.s;}}a[N];
int f[16005],q[16005];
int main()
{
    int m,n;qr(m),qr(n);
    for(int i=1;i<=n;i++)qr(a[i].l),qr(a[i].p),qr(a[i].s);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        int l=1,r=0;
        for(int k=max(0,a[i].s-a[i].l);k<a[i].s;k++)
        {
            while(l<=r&&f[q[r]]-q[r]*a[i].p<=f[k]-k*a[i].p)--r;
            q[++r]=k;
        }
        for(int j=a[i].s;j<=a[i].s+a[i].l-1&&j<=m;j++)
        {
            while(l<=r&&j-a[i].l>q[l])++l;
            f[j]=max(f[j],f[q[l]]+(j-q[l])*a[i].p);
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)ans=max(ans,f[i]);
    qw(ans);puts(""); 
    return 0;
}