记录编号	27644	评测结果	AWWWWWWWWW
题目名称	垃圾陷阱	最终得分	10
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	0.043 s
提交时间	2011-09-28 22:28:58	内存使用	0.65 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int D;//������
int G;//���ߤ���
class GOMI
{
public:
	int T;//���ߤϡ��r�g�ξ����Ͷ���z�ޤ줿
	int F;//�����S�֤��뤿��˕r�g�Οo�j
	int H;//���ߤϤθߤ���ߤ�뤳�Ȥ��Ǥ���
}LJ[101];

int A[1001][101];
long long live=10; //���T�ܻ�����r�g

int Compare ( const void *a , const void *b )
{
	return *(int *)a - *(int *)b;
}

void init()
{
	for (int i=0;i<=1000;i++)
		for (int j=0;j<=100;j++)
			A[i][j]=0;
			
	cin>>D>>G;
	for (int i=1;i<=G;i++)
		cin>>LJ[i].T>>LJ[i].F>>LJ[i].H;
	
	qsort(LJ+1,G,sizeof(GOMI),Compare);
	
	for (int i=1;i<=G;i++)
		live+=LJ[i].F;
}

void dp()
{
	A[0][10]=1;
	for (int i=1;i<=G;i++)
	{
		//for (int j=0;j<=D-1;j++)
		for (int j=D-1;j>=0;j--)
		{
			//for (int k>=LJ[i].T;k++)
			for (int k=live;k>=LJ[i].T;k--)
			{
				if (A[j][k]>0)
				{
					A[j][k+LJ[i].F]++;//�ԣ����|��
					A[j+LJ[i].H][k]++; //���ԣ��|��
					if (j+LJ[i].H >=D)
					{
						cout<<LJ[i].T<<endl;
						return;
					}
				}
			}
		}
	}

}

int main()
{
	freopen("well.in","r",stdin);
	freopen("well.out","w",stdout);
	init();
	dp();
	return 0;
}