rt

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, m, v[65], w[65], z[65], dp[65][32005];//物品数量，钱数，重要度，价格，种类 

signed main(){
	cin >> m >> n;
	for (int i = 1; i <= n; i++){
		cin >> w[i] >> v[i] >> z[i];
		v[i] *= w[i];
	} 
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (!z[i]){
				if (j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
				else dp[i][j] = dp[i - 1][j];
			}
			else{
				if (j < w[z[i]]) dp[i][j] = dp[i - 1][j];
				else if (j >= w[z[i]] && j <= w[z[i]] + w[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[z[i]]] + v[z[i]]);
				else if (j >= w[z[i]] + w[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[z[i]] - w[i]] + v[i] + v[z[i]]);
			}
		}
	}
	cout << dp[n][m];
	return 0;
}

本人是蒟蒻，求大佬帮助