← 返回题目列表

AtCoder · awc0009_d

D. 种植花卉种子

中文机器翻译题面 查看原题

分数: 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