建议添加hack数据，撒下所有题解并添加我的题解

1 1
1 1 1000000000

1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1010;
map<ll,vector<pair<ll,ll>>> g;
ll n,m,dp[N];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(ll i=1,a,b,c; i<=n; i++) {
		cin>>a>>b>>c;
		g[c].push_back({a,b});
	}
	for(auto vec:g)
		for(ll j=m; j>=0; j--)
			for(auto x:vec.second)
				if(j>=x.first)
					dp[j]=max(dp[j],dp[j-x.first]+x.second);
	cout<<dp[m];
	return 0;
}