A1627.摸鱼

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

狗星疫情期间,所有学校暂停线下课,改为线上课。AC狗不太自觉,线上课的时候老是摸鱼。

由于狗星教育局对安排线上课没有经验,导致有些课的时间重叠了,这给了AC狗更大的摸鱼机会。

AC狗每天共上课 TT 分钟,从第 11 分钟开始到第 TT 分钟结束。

假设某堂课于第 AA 分钟结束,时长 WW 分钟,该堂课于第 A+W1A+W-1 分钟结束。

AC狗只能在每堂课开始的时候进入课堂(过了时间不再允许进入直播间),并且要完整把这堂课上完,上课的时候如果其他课开始,他不用去上课。如果当前时刻AC狗并没有在上课,而且此时是某几堂课的开始时刻,那么他必须选择其中一堂去上课。

显然,选择上不同的课休息的时间不同,AC狗想尽可能多的时间用来摸鱼,请你帮他计算他最多能摸鱼多久?

输入格式

输入的第一行为两个整数 TNT、N,代表AC狗今天同上课 TT 分钟,共有 NN 堂课。

接下来 NN 行每行两个整数,分别是 A,WA,W ,代表这堂课从第 AA 分钟开始,上课时长 WW 分钟。

输出格式

输出为一行,代表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<=1041 <= T,N <= 10^4

1<=A<=T1<=A<=T

1<=A+W1<=T1<=A+W-1<=T

笑死

0/50
首页