全RE

#include "bits/stdc++.h"
#define int long long
using namespace std;
struct node{
	int v, p, q;
} a[100];
int n, m;
int dp1[5000005], dp2[5000005];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		cin >> a[i].v >> a[i].p >> a[i].q;
		a[i].p *= a[i].v;
	}
	for (int i = 1; i <= m; i++)
		if (a[i].q == 0){
			for (int j = 1; j <= 5000000; j++) dp2[i] = 0;
			for (int j = a[i].v; j <= n; j++)
				dp2[j] = dp1[j - a[i].v] + a[i].p;
			for (int j = 1; j <= m; j++)
				if (a[j].q == i)
					for (int k = n; k >= a[i].v + a[j].v; k++)
						dp2[k] = max(dp2[k], dp2[k - a[j].v] + a[j].p);
			for (int j = a[i].v; j <= n; j++)
				dp1[j] = max(dp1[j], dp2[j]);
		}
		cout << dp1[n];
	return 0;
}