记录编号	79564	评测结果	AAAAAAAAAA
题目名称	垃圾陷阱	最终得分	100
用户昵称	Launcher	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2013-11-05 22:01:57	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>

using namespace std;

int t[102]={0},h[102]={0},f[102]={0};
int a[1002]={0};
int n,m;
void sort(int l,int r)
{
	int i,j,x,y;
	i=l;
	j=r;
	x=t[(l+r)/2];
	do
	{
		while (t[i]<x) i++;
		while (t[j]>x) j--;
		if (i<=j)
		{
			y=t[i];
			t[i]=t[j];
			t[j]=y;
			
			y=h[i];
			h[i]=h[j];
			h[j]=y;
			
			y=f[i];
			f[i]=f[j];
			f[j]=y;
			
			i++;
			j--;
		}
	}
	while (i<=j);
	if (l<j) sort(l,j);
	if (i<r) sort(i,r);
}
int main()
{
	freopen("well.in","r",stdin);
	freopen("well.out","w",stdout);
	int i,j,k;
	cin>>m>>n;
	for (i=1;i<=n;i++)
		cin>>t[i]>>f[i]>>h[i];
	sort(1,n);

	a[0]=10;
	for (i=1;i<=n;i++)
	{
		for (j=m-1;j>=0;j--)
		{
			if ((a[j]!=0)&&(t[i]<=a[j]))
			{

				
				if (j+h[i]>=m)
				{
					cout<<t[i]<<endl;
					return 0;
				}
				if (a[j+h[i]]<a[j]) a[j+h[i]]=a[j];
				a[j]+=f[i];
			}
		}
		
	}
	int ans;
	ans=10;
	for (i=1;i<=n;i++)
	{
		if (t[i]-t[i-1]>ans)
		{
			cout<<t[i-1]+ans<<endl;
			return 0;
		}
		ans+=t[i-1]-t[i]+f[i];
	}
	cout<<t[n]+ans<<endl;
	return 0;
}