离散化了

#include <bits/stdc++.h>
using namespace std;
int n, m, v[1005], w[1005], f[1005][3], len = 1, dp[1000005];
void cz();
int main () {
	cin >> n >> m;
	cz();
	/*
	for ( int i = 1; i <= len; i++ ) {
	for ( int j = 0; j <= 2; j++ ) {
	cout << f[i][j] << " ";
	}
	cout << endl;
	}
	// */
	for ( int i = 1; i <= len; i++ ) {
		for ( int j = n; j >= v[f[i][0]]; j-- ) {
			int z = f[i][0], c1 = f[i][1], c2 = f[i][2];
			dp[j] = max ( dp[j], dp[j - v[z]] + w[z] );
			if ( j >= v[z] + v[c1] ) dp[j] = max ( dp[j], dp[j - v[z] - v[c1]] + w[z] + w[c1] );
			if ( j >= v[z] + v[c2] ) dp[j] = max ( dp[j], dp[j - v[z] - v[c2]] + w[z] + w[c2] );
			if ( j >= v[z] + v[c2] + v[c1] ) dp[j] = max ( dp[j], dp[j - v[z] - v[c2] - v[c1]] + w[c2] + w[z] + w[c2] );
		}
	}
	cout << dp[n];
	return 0;
}
void cz() {
	for ( int i = 1; i <= m; i++ ) {
		int p, q;
		cin >> w[i] >> p >> q;
		v[i] = w[i];
		w[i] *= p;
		if ( q == 0 ) f[i][0] = 1;
		else {
			if ( f[q][1] != 0 ) f[q][2] = i;
			else f[q][1] = i;
		}
	}
	if ( f[1][0] == 1 ) len = 2;
	for ( int i = 2; i <= m; i++ ) {
		if ( f[i][0] == 1 ) {
			if ( len != i ) {
				f[len][1] = f[i][1], f[len][2] = f[i][2];
				f[i][0] = f[i][1] = f[i][2] = 0;
			}
			f[len][0]=i,len++;
		}
	}
	len--;
}