答案大了，帮帮！！！

#include <iostream>
#include <algorithm>

using namespace std;

struct thing
{
	int v , p , q;
}things[100];

bool take[1000000][100];
int n , m , dp[1000000] , place[100];

bool cmp (thing a , thing b)
{
	return a.q < b.q;
}

int main()
{
	scanf("%d%d" , &n , &m);
	for (int i = 1 ; i <= m ; i++) scanf("%d%d%d" , &things[i].v , &things[i].p , &things[i].q);
	
	sort (things+1 , things+m+1 , cmp);
	
	for (int i = 1 ; i <= m ; i++)
	{
		for (int j = n ; j >= things[i].v ; j--)
		{
			if (things[i].q == 0) //主件 
			{
				if (dp[j-things[i].v] + (things[i].v * things[i].p) >= dp[j])
					dp[j] = dp[j-things[i].v] + things[i].v * things[i].p , take[j][i] = true;
				else
					take[j][i] = false;
			}
			else //附件 
			{
				if (take[j-things[i].v][things[i].q])
					dp[j] = max(dp[j] , dp[j-things[i].v] + (things[i].v * things[i].p)) , take[j][i] = true;
				else 
					take[j][i] = false;
			}
		}
	}
	
	cout << dp[n];
	
	return 0;
}