记录编号	232619	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	ミント	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2016-03-02 12:19:01	内存使用	0.40 MiB

//Code By Sekkai Ichiban No Mahou-Shounen;
#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

ifstream fin("budget.in");
ofstream fout("budget.out");

const int Maxn = 32000 + 10;
const int Maxm = 60 + 10;
int Main_Kount[Maxm], Fun[Maxn];
/*int Price_Main[Maxm], Price_1[Maxm], Price_2[Maxm], Price_12[Maxm];
int Impor_Main[Maxm], Impor_1[Maxm], Impor_2[Maxm], Impor_12[Maxm];*/
int N, M;
int V, P, Q;

class poi
{
    public:
		//int Main, One, Two, All;
		int Flag[4+1];
}Price[Maxm], Impor[Maxm];

void Init()
{
	/*memset(Main_Kount, 0, sizeof(Main_Kount));
	memset(Price_Main, 0, sizeof(Price_Main));
	memset(Price_1, 0, sizeof(Price_1));
	memset(Price_2, 0, sizeof(Price_2));
	memset(Price_12, 0, sizeof(Price_12));
	memset(Fun, 0, sizeof(Fun));*/
	
	memset(Price, 0, sizeof(Price));
	memset(Impor, 0, sizeof(Impor));
	memset(Main_Kount, 0, sizeof(Main_Kount));
	memset(Fun, 0, sizeof(Fun));
	
	return ;
}
void Judge_Sub()
{
	Price[Q].Flag[4] = Price[Q].Flag[2] + Price[Q].Flag[3] - Price[Q].Flag[1];
	Impor[Q].Flag[4] = Impor[Q].Flag[2] + Impor[Q].Flag[3] - Impor[Q].Flag[1];
	
	return ;
}
void Read()
{
	fin>>N>>M;
	
	for(int i=1;i<=M;i++)
	{
		fin>>V>>P>>Q;
		
		if(Q==0)
		{
			Main_Kount[i] = 1;
			Price[i].Flag[1] = V;
			Impor[i].Flag[1] = V * P;
			continue;
		}
		else
		{
			Main_Kount[Q]++;
			
			Price[Q].Flag[Main_Kount[Q]] = Price[Q].Flag[1] + V;
			Impor[Q].Flag[Main_Kount[Q]] = Impor[Q].Flag[1] + V * P;
			
			if(Main_Kount[Q]==3)
				Judge_Sub();
			continue;
		}
	}
	
	return ;
}
void Work()
{
	for(int i=1;i<=M;i++)
		for(int j=N;j>=Price[i].Flag[1];j--)
			if(Main_Kount[i]!=0)
				for(int Flag_Pos=1;Flag_Pos<=4;Flag_Pos++)
					if(j>=Price[i].Flag[Flag_Pos])
						Fun[j] = max(Fun[j-Price[i].Flag[Flag_Pos]] + Impor[i].Flag[Flag_Pos], Fun[j]);
	return ;
}
void Write()
{
	fout<<Fun[N]<<endl;
	
	return ;
}
int main()
{
	Init();
	
	Read();
	
	Work();
	
	Write();
	
	fin.close();
	fout.close();
	
	return 0;
}