#include <bits/stdc++.h> using namespace std; int m,n,p,K; int w[10001],c[10001],f[10001],stone[10001][1001]; int main() { scanf("%d%d",&m,&n); for(int i=1; i<=n; i++) { scanf("%d%d%d",&w[i],&c[i],&p); stone[p][++stone[p][0]]=i; K=max(K,p); //统计最多有多少组 } for(int k=1; k<=K; k++) //枚举组数 for(int j=m; j>=0; j--) //倒序枚举背包容量 for(int i=1; i<=stone[k][0]; i++) //枚举k组里的所有物品 if(w[stone[k][i]]<=j) //如果可以放 f[j]=max(f[j],f[j-w[stone[k][i]]]+c[stone[k][i]]); printf("%d\n",f[m]); }