#include<bits/stdc++.h> using namespace std; int m,n,temp=0; int f[1001][1001]; int a[10005]; 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(){ scanf("%d %d",&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){ a[bag[i].g]++; continue; } else{ if(a[bag[i].g]==1) bag[i].c=0; else{ a[bag[i].g]++; } } } for(int i=1;i<=10000;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]; } } printf("%d",f[n][m]); return 0; }