码风不好，请大佬们见谅。

#include<bits/stdc++.h>
using namespace std;
const int N=3200+100;
struct node
{
	int price;
	int degree;
}w[N];
int n,m,dp[N],num[N][N],vis[N];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int p=0;
		scanf("%d%d%d",&w[i].price,&w[i].degree,&p);
		if(p!=i&&p!=0)
			vis[i]=1,num[p][0]++,num[p][num[p][0]]=i;
	}
	
	//for(int i=1;i<=m;i++)
	//	printf("%d %d \n",num[i][1],num[i][2]);
		
	for(int i=1;i<=m;i++)
	{
		if(vis[i]) continue;
		for(int j=n;j>=w[i].price;j--)
		{
			dp[j]=max(dp[j],dp[j-w[i].price]+w[i].price*w[i].degree);
			
			if(num[i][0]==1)
			{
				int a=num[i][1];
				if(j>=w[i].price+w[a].price)
					dp[j]=max(dp[j],dp[j-w[i].price-w[a].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price));
			}
			if(num[i][0]==2)
			{
				int a=num[i][1],b=num[i][2];
				if(j>=w[i].price+w[a].price)
					dp[j]=max(dp[j],dp[j-w[i].price-w[a].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price));
				if(j>=w[i].price+w[b].price)
					dp[j]=max(dp[j],dp[j-w[i].price-w[b].price]+(w[i].degree*w[i].price)+(w[b].degree*w[b].price));
				if(j>=w[i].price+w[a].price+w[b].price)
					dp[j]=max(dp[j],dp[j-w[i].price-w[a].price-w[b].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price)+(w[b].degree*w[b].price));
			}
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}