2分qwq：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=10001,M=10001;
int w[N],s[1001],sl,g[1001][1001],ans[N][M],c[N];
int main(){
	cin >>m>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin >>w[i]>>c[i]>>x;
		s[x]++;
		g[x][s[x]]=i;
		sl=max(sl,x);
	}
	for(int i=1;i<=sl;i++){
		for(int j=m;j>=0;j--){
			for(int k=1;k<=s[i];k++)
			if(j>=w[i])ans[i][j]=max(ans[i-1][j-w[g[i][k]]]+c[g[i][k]],ans[i-1][j]);
			else ans[i][j]=ans[i-1][j];
		}
	}
	cout <<ans[n][m];
	return 0;
}