记录编号	294734	评测结果	AAAAAAAAAA
题目名称	尼克的任务	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-08-12 17:36:11	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
#define M(a,v) memset(a,v,sizeof(a))
const int maxn = 10010;
#define itn int
int n,m;
struct edge
{
	int to,next,dis;
}a[maxn*4];
int len=0, head[maxn];
void insert(int x,int y,itn z){
	a[++len].to=y; a[len].dis=z;
	a[len].next=head[x]; head[x]=len;
}
int s[maxn],t[maxn],dis[maxn];
bool Comp(const int &a,const int &b){
	if(a<b) return 1;
	else return 0;
}
int Merge(int x){
	int l=1,r=m+1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(t[x]<=s[mid]) r=mid-1;
		else l=mid+1;
	}
	return l;
}
void Spfa(int x){
	bool f[maxn]; M(f,0); f[x]=1;
	deque<int> q; q.push_back(x); 
	M(dis,63); dis[x]=0;
	while(!q.empty()){
		int k=q.front(); q.pop_front(); f[k]=0;
		for(int i=head[k];i;i=a[i].next){
			int p=a[i].to;
			if(dis[p]>dis[k]+a[i].dis){
				dis[p]=dis[k]+a[i].dis;
				if(!f[p]){
					f[p]=1;
					if(!q.empty() && dis[p]<dis[q.front()]) q.push_front(p);
					else q.push_back(p);
				}
			}
		}
	}
	printf("%d\n",n-dis[n]);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		insert(x-1,x+y-1,y);
		s[i]=x-1; t[i]=x+y-1;
	}
	sort(s+1,s+1+m,Comp);
	s[m+1]=n;
	for(int i=1;i<=m;i++){
		int temp=Merge(i);
		//printf("End=%d s=%d\n",t[i],s[temp]);
		if(s[temp]!=t[i]){
			insert(t[i],s[temp],0);
		}
	}
	if(s[1]!=0) insert(0,s[1],0);
	
	Spfa(0);
}



int Main(){
	freopen("lignja.in","r",stdin);
	freopen("lignja.out","w",stdout);
	init(); return 0;
}
int ZHOUYOUERZI=Main();
int main(){;}