#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int MAXN=1005,mod=998244353,inf=0x3f3f3f3f;
int n,m,f[MAXN],c[MAXN>>2][MAXN],w[MAXN>>2][MAXN],len[MAXN>>2],k=0;// k是背包组数，len[i]是第i组的数量
struct THING{
    int a,b,c;
    bool operator<(THING o)const{
        return c<o.c;
    }
}th[MAXN];
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>th[i].a>>th[i].b>>th[i].c;
    sort(th+1,th+n+1);
    for(int i=1;i<=n;i++){
        if(th[i].c!=th[i-1].c)
            len[++k]=0;
        c[k][++len[k]]=th[i].a;
        w[k][len[k]]=th[i].b;
    }
    for(int i=1;i<=k;i++)
        for(int t=1;t<=len[i];t++)
            for(int j=m;j>=c[i][t];j--)
                f[j]=max(f[j],f[j-c[i][t]]+w[i][t]);
    cout<<f[m]; 
    return 0;
}

分组背包都不会是不是可以退役了。