记录编号	49408	评测结果	AAAAAAAAAA
题目名称	尼克的任务	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2012-11-07 20:33:51	内存使用	3.30 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct typea
{
	int a,b,t;
}miss[10010];

int f[10010];

bool cmp(typea a,typea b)
{
	return(a.a>b.a);
}

int main(void)
{
	freopen("lignja.in","r",stdin);
	freopen("lignja.out","w",stdout);
	int i,j,lastj=0,n,m;
	bool run;
	cin>>n>>m;
	for (i=1;i<=m;i++)
	{
		cin>>miss[i].a>>miss[i].t;
		miss[i].b=miss[i].a+miss[i].t-1;
	}
	sort(miss+1,miss+1+m,cmp);
	for (i=n;i>=1;i--)
	{
		run=false;
		for (j=lastj+1;j<=m&&miss[j].a>=i;j++)
		{
			if (miss[j].a==i)
			{
				run=true;
				f[i]=max(f[i],f[miss[j].b+1]);
			}
			lastj=j;
		}
		if (!run)
			f[i]=f[i+1]+1;
	}
	cout<<f[1]<<endl;
	return(0);
}