#include<bits/stdc++.h> using namespace std; int m,n,p,K,w[10001],c[10001],f[10001],stone[10001][1001]; int main(){ cin>>m>>n; for(int i=1; i<=n; i++){ cin>>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++)if(w[stone[k][i]]<=j)f[j]=max(f[j],f[j-w[stone[k][i]]]+c[stone[k][i]]);//枚举组数|倒序枚举背包容量|枚举k组里的所有物品|如果可以放 cout<<f[m]; return 0; }