> #include <stdio.h>
> #include <iostream>
> using namespace std;
> 
> struct fence{
>     int l,p,s;
>     bool friend operator < (fence a,fence b)
>     {
>         return a.s<b.s;
>     }
> }w[101];
> 
> int main()
> {
>   //  freopen("in.txt","r",stdin);
>   //  freopen("out.txt","w",stdout);
>     int n,i,j,k,tmp;
>     int f[16010],g[16010];
>     while(scanf("%d%d",&n,&k)!=EOF){
>         for(i=0;i<k;i++) scanf("%d%d%d",&w[i].l,&w[i].p,&w[i].s);
>         sort(w,w+k);
>         // 初始处理
>         for(i=0;i<w[0].s;i++) f[i]=g[i]=0;
>         for(;i<=n;i++){
>             f[i]=i>w[0].l?w[0].l*w[0].p:i*w[0].p;
>             g[i]=0;
>         }
> //      for(i=0;i<=n;i++) printf("%d ",f[i]);
> //      printf("\n"); 
>         for(j=1;j<k;j++){    // 处理第二个以上的工人
>             for(i=w[j].s;i>=0;i--) g[i]=max(g[i+1]-w[j].p,f[i]); 
>             for(i=w[j].s+w[j].l-1;i>=w[j].s;i--){
>                 if(i>w[j].l) f[i]=g[i-w[j].l]+w[j].p*w[j].l;
>                 else {
>                     tmp=i>w[j].l?w[j].l*w[j].p:i*w[j].p;
>                     if(tmp>f[i]) f[i]=tmp;
>                 }
>             }
>             tmp=f[w[j].s+w[j].l-1];
>             for(i=w[j].s+w[j].l;i<=n;i++) f[i]=tmp;  // 向上更新
> //            printf("g\n");
> //            for(i=0;i<=n;i++) printf("%d ",g[i]);
> //            printf("\nf\n");
> //            for(i=0;i<=n;i++) printf("%d ",f[i]);
> //            printf("\n");
>         }
>         printf("%d\n",f[n]);
>     }
>     return 1;
> }