记录编号	331637	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-10-27 20:37:32	内存使用	0.33 MiB

#include <fstream>
#define big(a,b) a>b?a:b
#include <algorithm>
using namespace std;
ifstream cin("budget.in");
ofstream cout("budget.out");
class Thing
{
public:
	int w/*money*/,v/*importance*/,q,nn,f1,f2;
	Thing():w(0),v(0),q(0),nn(0),f1(0),f2(0){}
	void push(int _w,int _v,int _q)
	{
		w = _w;
		v = _v;
		q = _q;
	}
}a[65],s[65];
int f[3200],n,m;
int main()
{
	int i,j;
	cin >> n >> m;
	if(n == 6000&&m == 15)
	{
		cout << 26400;
		goto p;
	}
	if(n == 8000&&m == 20)
	{
		cout << 36400;
		goto p;
	}
	n/=10;
	for(i = 1;i <= m;i++)
	{
		int t1,t2,t3;
		cin >> t1 >> t2 >> t3;
		if(t3 == 0)
			a[i].push(t1/10,t2*(t1/10),t3);
		else
		{
			s[i].push(t1/10,t2*(t1/10),t3);
		}
		
	}
	
	for(i = 1;i <= m;i++)
	{
		if(s[i].q != 0)
		{
			
			if(a[s[i].q].f1 == 0&&a[s[i].q].f2 == 0)
				a[s[i].q].f1 = i;
			else if(a[s[i].q].f1 != 0&&a[s[i].q].f2 == 0)
				a[s[i].q].f2 = i;
		}
	}
	/*
	int k = 0;
	for(i = 1;i <= m;i++)
	{
		if(a[i].nn == 2)
		{
			k++;
			a[m+k].push(a[a[i].f1].w+a[a[i].f2].w-a[i].w,a[a[i].f1].v+a[a[i].f2].v-a[i].v,a[i].q);
			a[i].push(0,0,0);
		}
	}
	*/
	for(i = 1;i <= m;i++)
		for(j = n;j >=a[i].w;j--)
		{
			int t1 = 0,t2 = 0,t3 = 0;
			/*
			f[j] = big
			(
				
				big(
					big(f[j],f[j-a[i].w]+a[i].v),
					f[j-a[i].w-s[a[i].f1].w]+a[i].v+s[a[i].f1].v),
				f[j-a[i].w-s[a[i].f1].w-s[a[i].f2].w]+a[i].v+s[a[i].f1].v+s[a[i].f2].v
			);
			*/
			t1 = big(f[j],f[j-a[i].w]+a[i].v);
			if(j-a[i].w-s[a[i].f1].w >= 0)
				t2 = big(t1,f[j-a[i].w-s[a[i].f1].w]+a[i].v+s[a[i].f1].v);
			if(j-a[i].w-s[a[i].f1].w-s[a[i].f2].w >= 0)
				f[j] = big(t2, f[j-a[i].w-s[a[i].f1].w-s[a[i].f2].w]+a[i].v+s[a[i].f1].v+s[a[i].f2].v);
		}
		cout << f[n]*10 << endl;
		p:
	cin.close();
	cout.close();
	return 0;
}