A29831.网约车司机

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小码君兼职当网约车司机,它一天可以安排工作的时间为n分钟,从第1分钟开始到第n分钟结束。

现在平台派发了k个出行单,给出每个行程的开始时间p(分钟)和持续时间t(分钟),如果某行程第p分钟开始,持续时间为 t分钟,则该行程将在第 p+t-1分钟结束。

同时有多个单时,小码君只能选择一个,不同行程的起止时间都不能有重叠。因为工作时间越长,收入越高,小码君想知道它最多能工作多长时间。

输入格式

第一行含两个整数N和K,N表示小码君可以安排工作的时间,单位为分钟,K表示平台当天派发了k个出行单。

接下来共有K行,每一行有两个用空格隔开的整数p和t,表示该行程从小码君开始工作的第p分钟开始,持续时间为t分钟。

输出格式

仅一行,表示小码君在可以安排工作的时间内最多能工作多长时间。

输入输出样例

  • 输入#1

    60 5
    21 10
    28 9
    1 19
    30 8
    21 8

    输出#1

    35

说明/提示

1≤n≤100000,1≤k≤100000, 1≤p≤n,1≤t≤n。

首页