B - 会議室の空き時間 解説 /

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

配点 : 300 点

問題文

高橋君は、会社の会議室の予約管理を任されています。

会議室の利用可能時間は時刻 0 から時刻 T までの区間 [0, T] です。

今日の会議室には N 件の予約が入っています。i 番目の予約は時刻 S_i に開始し時刻 E_i に終了します。すなわち、i 番目の予約によって半開区間 [S_i, E_i) の時間帯が使用されます。予約の時間帯は互いに重なりません。ただし、予約は開始時刻の昇順に与えられるとは限りません。

利用可能時間 [0, T] のうち、どの予約にも使用されていない部分を空き時間と呼びます。高橋君は、急遽開催することになった打ち合わせのために、できるだけ長い連続した空き時間を確保したいと考えています。

今日の会議室における最も長い連続した空き時間の長さを求めてください。空き時間が存在しない場合は 0 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 0 \leq S_i < E_i \leq T (1 \leq i \leq N)
  • 予約の時間帯は互いに重ならない。すなわち、i \neq j ならば半開区間 [S_i, E_i) と半開区間 [S_j, E_j) は共通部分を持たない
  • 入力はすべて整数

入力

N T
S_1 E_1
S_2 E_2
\vdots
S_N E_N
  • 1 行目には、予約の件数を表す整数 N と、会議室の利用可能終了時刻を表す整数 T が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各予約の開始時刻と終了時刻が与えられる。
  • 1 + i 行目では、i 番目の予約の開始時刻 S_i と終了時刻 E_i がスペース区切りで与えられる。

出力

最も長い連続した空き時間の長さを 1 行で出力してください。空き時間が存在しない場合は 0 を出力してください。

入力例 1

3 10
1 3
5 6
8 9

出力例 1

2

入力例 2

5 100
0 10
20 35
40 60
70 85
95 100

出力例 2

10

入力例 3

4 1000000000
100000000 200000000
300000000 400000000
600000000 700000000
900000000 950000000

出力例 3

200000000

Score : 300 pts

Problem Statement

Takahashi is in charge of managing meeting room reservations at his company.

The meeting room is available during the interval [0, T], from time 0 to time T.

There are N reservations for the meeting room today. The i-th reservation starts at time S_i and ends at time E_i. That is, the i-th reservation occupies the half-open interval [S_i, E_i). The time intervals of the reservations do not overlap with each other. However, the reservations are not necessarily given in ascending order of start time.

Among the available time [0, T], the portions not used by any reservation are called free time. Takahashi wants to secure the longest possible continuous free time for a meeting that was suddenly scheduled.

Find the length of the longest continuous free time in today's meeting room. If there is no free time, output 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 0 \leq S_i < E_i \leq T (1 \leq i \leq N)
  • The time intervals of the reservations do not overlap. That is, if i \neq j, then the half-open intervals [S_i, E_i) and [S_j, E_j) have no common part.
  • All inputs are integers.

Input

N T
S_1 E_1
S_2 E_2
\vdots
S_N E_N
  • The first line contains an integer N representing the number of reservations and an integer T representing the end of the meeting room's available time, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the start time and end time of each reservation are given.
  • The (1 + i)-th line contains the start time S_i and end time E_i of the i-th reservation, separated by a space.

Output

Output the length of the longest continuous free time in a single line. If there is no free time, output 0.

Sample Input 1

3 10
1 3
5 6
8 9

Sample Output 1

2

Sample Input 2

5 100
0 10
20 35
40 60
70 85
95 100

Sample Output 2

10

Sample Input 3

4 1000000000
100000000 200000000
300000000 400000000
600000000 700000000
900000000 950000000

Sample Output 3

200000000