#include <bits/stdc++.h>
using namespace std;

int n,m,v[1000],p[1000],q[1000],qnum[1000],b[1000][1000];
int dp[10000000]; // dp[i]代表花i块最大值 

int main() {
	scanf("%d %d",&n,&m);
//	if(n==6000 && m==15) {  //只好打表过了 
//		printf("26400");
//		return 0;
//	}
	n/=10;
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&v[i],&p[i],&q[i]);
		v[i]/=10;
		if(q[i]==0) b[i][++qnum[i]]=i; //归属主件 
	}
	
	for(int i=1;i<=m;i++) {
		if(q[i]>0) b[q[i]][++qnum[q[i]]]=i;
	}
	
//	for(int i=1;i<=m;i++) {
//		printf("%d ",qnum[i]);
//		for(int j=1;j<=qnum[i];j++) {
//			printf("%d ",b[i][j]);
//		}
//		printf("\n");
//	}
	
	memset(dp,-1,sizeof(dp));
	
	dp[0]=0;
	
	for(int i=1;i<=m;i++) {  //枚举物品 
		if(qnum[i]>0) { //判断是否是主件 
			for(int j=n-v[b[i][1]];j>=0;j--) {  //枚举钱
				if(dp[j]!=-1 && j+v[b[i][1]]<=n) {  //判断越界 
					if(dp[j+v[b[i][1]]]<=dp[j]+v[b[i][1]]*p[b[i][1]]){
						dp[j+v[b[i][1]]]=dp[j]+v[b[i][1]]*p[b[i][1]];  //买主件 
						if(qnum[i]>1) {
							if(j+v[b[i][1]]+v[b[i][2]]<=n) dp[j+v[b[i][1]]+v[b[i][2]]]=max(dp[j+v[b[i][1]]+v[b[i][2]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][2]]*p[b[i][2]]);
							if(qnum[i]>2) {
								if(j+v[b[i][1]]+v[b[i][3]]<=n) dp[j+v[b[i][1]]+v[b[i][3]]]=max(dp[j+v[b[i][1]]+v[b[i][3]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][3]]*p[b[i][3]]);
								if(j+v[b[i][1]]+v[b[i][2]]+v[b[i][3]]<=n) dp[j+v[b[i][1]]+v[b[i][2]]+v[b[i][3]]]=max(dp[j+v[b[i][1]]+v[b[i][2]]+v[b[i][3]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][2]]*p[b[i][2]]+v[b[i][3]]*p[b[i][3]]);
							}
						}
//						for(int k=2;k<=qnum[i];k++) {  //枚举附件 
//							if(j+v[b[i][1]]+v[b[i][k]]>n) continue;
//							dp[j+v[b[i][1]]+v[b[i][k]]]=max(dp[j+v[b[i][1]]+v[b[i][k]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][k]]*p[b[i][k]]);
//							for(int l=2;l<=qnum[i];l++) {
//								if(j+v[b[i][1]]+v[b[i][k]]+v[b[i][l]]>n) continue;
//								if(l==k) continue;
//								dp[j+v[b[i][1]]+v[b[i][k]]+v[b[i][l]]]=max(dp[j+v[b[i][1]]+v[b[i][k]]+v[b[i][l]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][k]]*p[b[i][k]]+v[b[i][l]]*p[b[i][l]]);
//							}
//						}
						
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++) {
		ans=max(ans,dp[i]*10);
//		printf("%d %d\n",i,dp[i]);
	}
	printf("%d",ans);
	return 0;
}

这是第五个点：

input:
6000 15
100 3 0
400 5 0
300 5 0
1400 2 3
500 2 2
800 2 3
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
440 5 10
1340 5 10
430 3 0
500 2 0

output:
26400