A1407 | 摸鱼
来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
狗星疫情期间，所有学校暂停线下课，改为线上课。AC狗不太自觉，线上课的时候老是摸鱼。
由于狗星教育局对安排线上课没有经验，导致有些课的时间重叠了，这给了AC狗更大的摸鱼机会。
AC狗每天共上课 $T$ 分钟，从第 $1$ 分钟开始到第 $T$ 分钟结束。
假设某堂课于第 $A$ 分钟开始，时长 $W$ 分钟，该堂课于第 $A+W-1$ 分钟结束。
AC狗只能在每堂课开始的时候进入课堂（过了时间不再允许进入直播间），并且要完整把这堂课上完，上课的时候如果其他课开始，他不用去上课。如果当前时刻AC狗并没有在上课，而且此时是某几堂课的开始时刻，那么他必须选择其中一堂去上课。
显然，选择上不同的课休息的时间不同，AC狗想尽可能多的时间用来摸鱼，请你帮他计算他最多能摸鱼多久？
由于狗星教育局对安排线上课没有经验，导致有些课的时间重叠了，这给了AC狗更大的摸鱼机会。
AC狗每天共上课 $T$ 分钟，从第 $1$ 分钟开始到第 $T$ 分钟结束。
假设某堂课于第 $A$ 分钟开始，时长 $W$ 分钟，该堂课于第 $A+W-1$ 分钟结束。
AC狗只能在每堂课开始的时候进入课堂（过了时间不再允许进入直播间），并且要完整把这堂课上完，上课的时候如果其他课开始，他不用去上课。如果当前时刻AC狗并没有在上课，而且此时是某几堂课的开始时刻，那么他必须选择其中一堂去上课。
显然，选择上不同的课休息的时间不同，AC狗想尽可能多的时间用来摸鱼，请你帮他计算他最多能摸鱼多久？
输入格式
输入的第一行为两个整数 $T、N$，代表AC狗今天同上课 $T$ 分钟，共有 $N$ 堂课。
接下来 $N$ 行每行两个整数，分别是 $A,W$ ，代表这堂课从第 $A$ 分钟开始，上课时长 $W$ 分钟。
接下来 $N$ 行每行两个整数，分别是 $A,W$ ，代表这堂课从第 $A$ 分钟开始，上课时长 $W$ 分钟。
输出格式
输出为一行，代表AC狗最长的摸鱼时间。
输入输出样例
输入 #1
10 3 1 5 1 4 5 5
输出 #1
5
输入 #2
14 7 1 3 1 2 3 5 3 4 4 8 6 2 7 3
输出 #2
7
【数据规模】
对于百分百的数据
$1 <= T,N <= 10^4$
$1<=A<=T$
$1<=A+W-1<=T$
对于百分百的数据
$1 <= T,N <= 10^4$
$1<=A<=T$
$1<=A+W-1<=T$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？