A3336. 网约车司机
编程题
入门
知识点
题目描述
小码君兼职当网约车司机，它一天可以安排工作的时间为n分钟，从第1分钟开始到第n分钟结束。
现在平台派发了k个出行单，给出每个行程的开始时间p(分钟)和持续时间t(分钟)，如果某行程第p分钟开始，持续时间为 t分钟，则该行程将在第 p+t-1分钟结束。
同时有多个单时，小码君只能选择一个，不同行程的起止时间都不能有重叠。因为工作时间越长，收入越高，小码君想知道它最多能工作多长时间。
现在平台派发了k个出行单，给出每个行程的开始时间p(分钟)和持续时间t(分钟)，如果某行程第p分钟开始，持续时间为 t分钟，则该行程将在第 p+t-1分钟结束。
同时有多个单时，小码君只能选择一个，不同行程的起止时间都不能有重叠。因为工作时间越长，收入越高，小码君想知道它最多能工作多长时间。
输入格式
第一行含两个整数N和K，N表示小码君可以安排工作的时间，单位为分钟，K表示平台当天派发了k个出行单。
接下来共有K行，每一行有两个用空格隔开的整数p和t，表示该行程从小码君开始工作的第p分钟开始，持续时间为t分钟。
接下来共有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。