不多说，上代码

#include<iostream>
using namespace std;
int t[320300],c[320100],q[321000],jg[320100],jg1[320100],jg2[320100],f[320100]={};
int dp[390050];
inline int maxx(int x,int y)
{
	return x>y?x:y;
}
int main()
{
	int n,m,k=0,cnt=0;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>c[i]>>q[i];
		if(q[i]!=0)
			f[q[i]]++;
		jg[i]=t[i]*c[i];
		if(f[q[i]]==1&&q[i]!=0)
			jg1[i]=t[i]*c[i];
		if(f[q[i]]==2&&q[i]!=0)
			jg2[i]=t[i]*c[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(cnt==i){
			cnt=0;
			k=0;
			continue;
		}
//		cout<<endl;
		for(int j=m;j>=t[i];j--)
		{
			if(f[i]==0&&q[i]==0)
			{
				dp[j]=maxx(dp[j],dp[j-t[i]]+jg[i]);
//				cout<<dp[j]<<" ";
			}
			else if(q[i]!=0)
			{
				if(f[q[i]]==1)
				{
					if(j>=(t[i]+t[q[i]]))
					dp[j]=maxx(dp[j],maxx(dp[j-t[q[i]]]+jg[q[i]],dp[j-(t[i]+t[q[i]])]+jg1[i]+jg[q[i]]));
					else if(j>=t[q[i]])
					dp[j]=maxx(dp[j],dp[j-t[q[i]]+jg[q[i]]]);
//					cout<<dp[j]<<" ";
				}
				else
				{
					for(int ans=i+1;ans<=n;ans++)
						if(q[ans]==q[i])
						{
							k=ans;
							cnt=ans;
							break;
						}
					if(j>=(t[i]+t[q[i]]+t[k]))
						dp[j]=maxx(dp[j],maxx(maxx(dp[j-t[q[i]]]+jg[q[i]],dp[j-(t[i]+t[q[i]])]+jg1[i]+jg[q[i]]),dp[j-(t[i]+t[q[i]]+t[k])]+jg[q[i]]+jg1[i]+jg2[k]));
					else if(((j>=(t[i]+t[q[i]]))||(j>=(t[q[i]]+t[k])))&&j<(t[i]+t[q[i]]+t[k]))
					{
						if(j<(t[i]+t[q[i]]))
						dp[j]=maxx(dp[j],dp[j-(t[q[i]]+t[k])]+jg[q[i]]+jg2[k]);
						else if(j<(t[q[i]]+t[k]))
						dp[j]=maxx(dp[j],dp[j-(t[i]+t[q[i]])]+jg[q[i]]+jg1[k]);
						else if(((j>=(t[i]+t[q[i]]))&&(j>=(t[q[i]]+t[k]))))
						dp[j]=maxx(dp[j],maxx(dp[j-(t[q[i]]+t[k])]+jg[q[i]]+jg2[k],dp[j-(t[i]+t[q[i]])]+jg[q[i]]+jg1[i]));
						else if(j>=t[q[i]])
						dp[j]=maxx(dp[j],dp[j-t[q[i]]+jg[q[i]]]);
//						cout<<dp[j]<<" ";
					}
				}
			}
		}
	}
	cout<<dp[m];
	return 0;
}