记录编号	318710	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-10-09 20:25:24	内存使用	1.23 MiB

/*
  Name: 金明的预算方案 
  Copyright: 
  Author: Go灬Fire 
  Date: 09/10/16 20:23
  Description: 题目描述，只可能有零个 一个 或 两个附件 
               手动分组，最多四种情况  1.一个主件 2.一主一副a 3.一主一副b 4.一主两副 
               然后就是一个很裸的背包！ 
*/
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#define Begin freopen("budget.in","r",stdin);freopen("budget.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=1010;
int tot,n,w[maxn],v[maxn],fu[maxn][3];
int _w[maxn][10],_v[maxn][10],num[maxn];
int f[250000];
bool zhu[maxn];
void Init();
//题目描述，只可能有零个 一个 或 两个附件 
int main(){
    Begin;
    Init();
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d%d",&tot,&n);
	for(int i=1;i<=n;i++){
		int x;scanf("%d%d%d",&w[i],&v[i],&x);
		v[i]*=w[i];
		if(x)fu[x][++fu[x][0]]=i;
		else zhu[i]=1;
	}
	int cnt=0,k;
	for(int i=1;i<=n;i++){
		if(zhu[i]){
			_w[++cnt][1]=w[i];
			_v[cnt][1]=v[i];
			num[cnt]=1;
			if(fu[i][0]>=1){
				_w[cnt][2]=w[fu[i][1]]+w[i];
				_v[cnt][2]=v[fu[i][1]]+v[i];
				num[cnt]=2;
			}
			if(fu[i][0]==2){
				_w[cnt][3]=w[fu[i][2]]+w[i];
				_w[cnt][3]=w[fu[i][2]]+v[i];
				_w[cnt][4]=w[fu[i][2]]+w[fu[i][1]]+w[i];
				_v[cnt][4]=v[fu[i][2]]+v[fu[i][1]]+v[i];
				num[cnt]=4;
			}
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=tot;j>=0;j--){
			for(int k=1;k<=num[i];k++){
				if(j-_w[i][k]<0)continue;
				f[j]=max(f[j],f[j-_w[i][k]]+_v[i][k]);
				//printf("%d ",f[j]);
			}
		}
	}
	printf("%d\n",f[tot]);
}