D - 花の種まき 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は庭に N 個の花の種を植えようとしています。

日付は第 1 日目、第 2 日目、…と続きます。高橋君は第 1 日目から順に各日について、種を植えられるかどうかを判断していきます。

天気予報によると M 回の雨の期間が予定されており、i 番目の雨の期間は第 L_i 日から第 R_i 日まで（両端を含む）続きます。ある日が M 回の雨の期間のうち少なくとも 1 つに含まれている場合、その日は雨の日です。雨の日は地面がぬかるんで作業ができないため、種を植えることができません。雨の日でない日には、種をちょうど 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
  • 1 行目には、植える種の数を表す整数 N と、雨の期間の数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から M 行にわたって、各雨の期間の情報が与えられる。1 + i 行目には、i 番目の雨の期間の開始日 L_i と終了日 R_i が、スペース区切りで与えられる。これは、第 L_i 日から第 R_i 日まで（両端を含む）雨が降ることを意味する。

出力

N 個すべての種を植え終える日の番号を 1 行で出力せよ。

入力例 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

Score : 366 pts

Problem Statement

Takahashi is trying to plant N flower seeds in his garden.

Days are numbered as day 1, day 2, and so on. Starting from day 1, Takahashi decides for each day whether he can plant a seed or not.

According to the weather forecast, there are M rainy periods scheduled. The i-th rainy period lasts from day L_i to day R_i (inclusive). A day is a rainy day if it is included in at least one of the M rainy periods. On rainy days, the ground is muddy and work cannot be done, so no seeds can be planted. On days that are not rainy, exactly 1 seed is planted.

Note that rainy periods may overlap with each other or one may be entirely contained within another. Even in such cases, any day that falls within any rainy period is treated as a rainy day.

Since the rainy periods are finite, all days after the last rainy period ends will be sunny, and given enough days, all seeds will eventually be planted.

Determine on which day all N seeds will have been planted.

Constraints

  • 1 \leq N \leq 10^9
  • 0 \leq M \leq 10^5
  • 1 \leq L_i \leq R_i \leq 10^{18}
  • The rainy periods are not necessarily sorted
  • All input values are integers

Input

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains an integer N representing the number of seeds to plant and an integer M representing the number of rainy periods, separated by a space.
  • The following M lines provide information about each rainy period. The (1 + i)-th line contains the start day L_i and end day R_i of the i-th rainy period, separated by a space. This means it rains from day L_i to day R_i (inclusive).

Output

Print on a single line the day number on which all N seeds have been planted.

Sample Input 1

5 2
2 4
7 7

Sample Output 1

9

Sample Input 2

10 3
3 8
5 12
20 25

Sample Output 2

26

Sample Input 3

1000000000 3
1 500000000
500000000001 999999999999
1000000000002 1000000000002

Sample Output 3

1500000000