#include<bits/stdc++.h> using namespace std; const int N=1009; int w[N][N],c[N][N], size[N],f[N][N],mc,maxn; int main(){ int n,m; cin>>m>>n; for(int i=1;i<=n;i++){ int a,b,l; cin>>a>>b>>l; w[++size[l]][l]=a; c[size[l]][l]=b; mc=max(mc,l); } for(int i=1;i<=mc;i++){ for(int j=1;j<=size[i];j++){ for(int k=0;k<=m;k++){ if(k>=w[j][i])f[i][k]=max(f[i-1][k],f[i-1][k-w[j][i]]+c[j][i]); else f[i][k]=f[i-1][k]; maxn=max(f[i][k],maxn); } } } cout<<maxn; }