分数: 366 分
问题陈述
高桥正在尝试种植 N 他花园里的花种子。
天数为天 1, 天 2,等等。从当天开始 1,高桥每天都会决定是否可以种下种子。
根据天气预报,有 M 预定的雨季。的 i-第一个雨期从日开始 L_i 到今天 R_i (含)。一天是一个 下雨天 如果它至少包含在其中之一中 M 雨季。下雨天,地里泥泞,无法干活,就无法播种。正好在不下雨的日子里 1 种子已种下。
请注意,雨季可能会相互重叠,或者一个雨季可能完全包含在另一个雨季中。即使在这种情况下,任何雨期内的任何一天都被视为雨天。
由于雨季是有限的,最后一次雨季结束后的所有日子都是晴天,只要有足够的天数,所有的种子最终都会播种。
确定在哪一天所有 N 种子已经种下。
约束
- 1 \leq N \leq 10^9
- 0 \leq M \leq 10^5
- 1 \leq L_i \leq R_i \leq 10^{18}
- 雨季不一定排序
- 所有输入值均为整数
输入
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
- 第一行包含一个整数 N 代表要种植的种子数量和一个整数 M 代表雨季数量,以空格分隔。
- 以下 M 行提供有关每个雨季的信息。的 (1 + i)- 第行包含开始日期 L_i 和结束日 R_i 的 i- 第一个雨季,以空格分隔。这意味着从白天开始就下雨 L_i 到今天 R_i (含)。
输出
在单行上打印所有日期 N 种子已经种下。
示例输入 1
5 2 2 4 7 7
示例输出 1
9
示例输入 2
10 3 3 8 5 12 20 25
示例输出 2
26
示例输入 3
1000000000 3 1 500000000 500000000001 999999999999 1000000000002 1000000000002
示例输出 3
1500000000