/ Vijos / 题库 /

可怜的Oliver

可怜的Oliver

描述

放苍蝇事件最终还是被Oliver知道了,精明的Oliver还调查出了放苍蝇的人是XX,他要严厉的惩罚XX,惩罚XX写作业,布置给XX比平常多几十倍几百倍的作业,在假期的任意时刻他都有可能布置作业,天哪,XX的黄金周又泡汤啦。XX的原计划有N分钟够他游玩,可是他必须服从Oliver,先做作业然后玩,从第一分钟开始到第N分钟结束。当XX从放假的第一分钟起就要开始赶作业。如果在同一时刻有多个作业需要完成,XX可以选其中的一个来做,而其余的则可以由其他的同学帮他来完成,反之如果只有一个作业,则该作业必须由XX去完成,假如某些作业开始时刻XX正在工作,则这些作业也由XX的同学来帮他完成。如果某作业于第P分钟开始,持续时间为T,则该作业将在第P+T-1分钟结束。

格式

输入格式

输入数据第一行含两个用空格隔开的整数N和K,N表示XX的原计划玩的时间长(以分钟为单位),K表示Oliver布置的作业总数。接下来共有K行,每一行有两个用空格隔开的整数P和T,表示Oliver老师布置的作业从第P分钟开始,持续时间为T分钟,其中N,K<=10000。

输出格式

输出文件仅一行包含一个整数,表示XX可能获得的最大空暇的时间。

样例1

样例输入1

15 6
1 2
1 6
4 11
8 5
8 1
11 5

样例输出1

4

限制

每个测点1s

提示

N,K<=10000

来源

冰尘e溶化邀请赛第二题,goleenuoer原创题

信息

ID
1577
难度
3
分类
动态规划 | 动态规划 | LIS 点击显示
标签
(无)
递交数
1413
已通过
739
通过率
52%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库