部分背包

#include<bits/stdc++.h>
using namespace std;
vector<int> v[100], w[100];
int n, m, dp[32768];
int main(){
	cin >> m >> n;
	for(int i = 1; i <= n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		if(z != 0){
			for(int j : v[z]) v[z].push_back(x*y+j);
			for(int j : w[z]) w[z].push_back(x+j);
		}
		else{
			v[i].push_back(x*y);
			w[i].push_back(x);
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = m; j >= 0; j--)
			for(int k = 0; k < v[i].size(); k++)
				if(j >= w[i][k]) dp[j] = max(dp[j], dp[j-w[i][k]]+v[i][k]);
	cout << dp[m];
	return 0;
}