/ Vijos / 题库 /

生产武器

生产武器

描述

最近,飞过海在OI总部总算弄了个小差,现在他又被调去了OI防卫部门来制造对付基德的工具(飞过海:最近真忙啊=.=).当然,这些工作是在OI总部内的机器上进行的.可是飞过海从来没有此经验(飞过海:囧);现在飞过海又接到了一批新的任务,现在他要编程来控制机器。已知机器一天工作N mins。当飞过海按动开始按钮的时候机器就开始运转。现在OI总司给了K个生产目标,可是只有一台机器,所以总司希望知道最少机器能生产多少个零件(也就是最少工作多少分钟)。如果同时有许多的零件要加工,机器只能选择一个。但是一个零件任务是有时间限制的,也就是说,1个零件必须从P分开始,持续T分钟(好牵强的规定啊!)。

由于飞过海很忙,所以请你来编写一下这个程序吧!o(^-^)o

格式

输入格式

第一行含两个整数N和K(1≤N≤10000000,1≤K≤100000),N表示机器的运转时间(由于机器要维护,它只能工作那么多时间),单位为分钟,K表示总司布置的零件总数。

接下来共有K行,每一行有两个用空格隔开的整数P和T,表示该任务从第P分钟开始,持续时间为T分钟.

输出格式

仅一行,表示机器最多可能加工零件的时间。(SO EASY =.=);

样例1

样例输入1

1 1
1 1

样例输出1

1

限制

各个测试点1s

来源

from 飞过海

信息

ID
1634
难度
7
分类
动态规划 点击显示
标签
(无)
递交数
1231
已通过
226
通过率
18%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

飞过海第一次模拟赛&OI总部对抗赛