分组背包（模板）

//考验心境的时候到了 
//和人比惨，痛苦减半 
#include<bits/stdc++.h>
using namespace std;
namespace{
    template<typename T>
    inline void read(T &s){
        T f=1;s=0;char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) s=(s<<1)+(s<<3)+(ch^48);
        s*=f;
    }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define low x&-x
int m,n,t;
int v[1005],w[1005],a[1005][1005],num[1005];
int f[1005];   //f[k][v]表示前k组物品花费费用v能取得的最大权值 
int main(){
    read(m);read(n);
    for(int i=1;i<=n;++i){
        int x;
        read(v[i]);read(w[i]);
        read(x);
        t=max(t,x);
        num[x]++;  //记录第x组元素的个数
        a[x][num[x]]=i;  //记录第x组第num[x]个元素在v[i]和w[i]的下标
    }
    for(int k=1;k<=t;++k){
        for(int j=m;j>=0;--j){
            for(int i=1;i<=num[k];++i){
                if(j>=v[a[k][i]])
                  f[j]=max(f[j],f[j-v[a[k][i]]]+w[a[k][i]]);//f[k][v]=max(f[k-1][v],f[k-1][j-v[a[k][i]]+w[a[k][i]] |物品i属于组k) 
            }
        }
    }
    cout << f[m];
    return 0;
}