记录编号	29313	评测结果	AAAAAAAAAA
题目名称	垃圾陷阱	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2011-10-21 12:17:15	内存使用	0.27 MiB

#include <iostream>   
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;   
int a,b,c,d,l,m,t=10,k[101];   
bool bo=false;   
struct fun
{
	int x;
	int y;
	int z;
}f[100];
int Compare(const void *elem1,const void *elem2)
{
	struct fun *elem3=(struct fun *)elem1;
	struct fun *elem4=(struct fun *)elem2;
	return (elem3->x > elem4->x) ?1:-1;
} 
int main(void)   
{   
    freopen ("well.in","r",stdin);   
    freopen ("well.out","w",stdout);   
    scanf("%d%d",&b,&c);   
    for (d=0;d<c;d++) scanf("%d%d%d",&f[d].x,&f[d].y,&f[d].z);   
	qsort(f,c,sizeof(fun),Compare);
	k[0]=10;
	for (d=0;d<c;d++)
	{
		bo=false;
		for (l=b;l>=0;l--)
			if (k[l]>=f[d].x)
			{
				if (l+f[d].z>=b)
				{
					printf("%d",f[d].x);
					goto end;
				}
				if (k[l]>k[l+f[d].z]) k[l+f[d].z]=k[l];
				k[l]+=f[d].y;
				bo=true;
			}
		if (!bo) break;
	}
	printf("%d",k[0]);
	end:
    fclose(stdin);   
    fclose(stdout);  
    return 0;   
}