https://www.luogu.com.cn/problem/P1280

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
inline int read(){
	int f=1,num=0;
	char rd=getchar();
	while(!isdigit(rd)){
		if(rd=='-') f=-1;
		rd=getchar();
	}
	while(isdigit(rd)){
		num=num*10+rd-48;
		rd=getchar();
	}
	return f*num;
}
pair<int,int> work[10090];
int dp[10090];
int main()
{
    int n=read(),k=read();
    for(int i=1;i<=n;i++) dp[i]=-111111111;
    for(int i=1;i<=k;i++) work[i].first=read()-1,work[i].second=read();
    sort(work+1,work+1+k);
    int pos=1;
    for(int i=0;i<n;i++){
        if(work[pos].first==i){
            while(work[pos].first==i){
                dp[i+work[pos].second]=max(dp[i+work[pos].second],dp[i]);
                pos++;
            }
        }
        else{
            dp[i+1]=max(dp[i]+1,dp[i+1]);
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}