#3WA求助

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,c[70][4],w[70][4],f[32005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(z==0){
            w[i][0]=x;c[i][0]=y*x;
        }else{
            if(c[z][1]==0){
                c[z][1]=y*x+c[z][0];
                w[z][1]=x+w[z][0];
            }else{
                c[z][2]=y*x+c[z][0];c[z][3]=c[z][1]+y*x;
                w[z][2]=x+w[z][0];w[z][3]=w[z][1]+x;
            }
        }
    }
/*  for(int i=1;i<=m;i++){
        for(int j=0;j<4;j++){
            if(c[i][j]==0)break;
            printf("%d %d\n",c[i][j],w[i][j]);
        }
    }*/
    for(int i=1;i<=m;i++){
        if(c[i][0]){
            for(int v=n;v>0;v-=10){
                for(int k=0;c[i][k];k++){
                    if(v>=w[i][k])f[v]=max(f[v],f[v-w[i][k]]+c[i][k]);
                }
            }
//          printf("%d\n",f[n]);
        }
    }
    printf("%d\n",f[n]);
    return 0;
}