#include<bits/stdc++.h> using namespace std; int m,n,temp=0; int f[1001][1001]; struct Bag{ int w; int c; int g; bool p=true; }bag[10005]; bool cmp(Bag a,Bag b){ if(a.p==false&&b.p==false)return 1; else if(a.p==false)return 0; else if(b.p==false)return 1; else return a.c>b.c; } int main(){ cin>>m>>n; for(int i=1;i<=n;i++){ scanf("%d %d %d",&bag[i].w,&bag[i].c,&bag[i].g); if(bag[i].w>m) bag[i].p=false; } stable_sort(bag+1,bag+1+n,cmp); for(int i=1;i<=n;i++){ if(i-1==0){ temp=bag[i].g; continue; } else if(bag[i].g==temp){ bag[i].c=0; }else{ temp=bag[i].g; } } for(int i=1;i<=100;i++){ for(int j=1;j<=m;j++){ if(j>=bag[i].w){ f[i][j]=max(f[i-1][j],f[i-1][j-bag[i].w]+bag[i].c); } else f[i][j]=f[i-1][j]; } } cout<<f[n][m]<<endl; return 0; }