#P1017. 伴舞僵尸的进攻

伴舞僵尸的进攻

"僵王博士又来了!这次他带来了他的太空步军团!" —— 疯狂戴夫

题目背景

那是一个风雨交加的夜晚,疯狂戴夫正在前院照料他的豌豆射手。突然,远处的草坪上传来了迪斯科球的闪光和震耳欲聋的音乐声——是僵王博士的太空步僵尸军团!僵王博士站在屋顶上,挥舞着指挥棒,派出了 nn 只伴舞僵尸作为先头部队。

这些伴舞僵尸穿着闪亮的舞衣,踩着迈克尔·杰克逊的太空步,试图用舞蹈征服戴夫的草地。当动感的音乐响起,伴舞僵尸们将按照既定的节奏陆续登场,然后开始召唤更多的舞伴,向四面八方扩散。

戴夫看着他的向日葵们吓得瑟瑟发抖,叹了口气:"我需要知道,这些家伙到底要跳多久才能占满整个院子……"

题面描述

具体规则如下:

  • 第 ii 只伴舞僵尸将在第 aia_i 秒出现于数轴上的坐标 bib_i 处。
  • 每一只位于坐标 xx 的伴舞僵尸,在它出现的一秒后以及此后的每一秒,都会在其相邻的两个整数坐标 x−1x-1 和 x+1x+1 处各召唤一只新的伴舞僵尸。被新召唤的伴舞僵尸同样拥有上述召唤能力,且同一个坐标处可以同时存在多只伴舞僵尸。

僵王博士的目标是用伴舞僵尸覆盖整个战场。问:至少需要多少秒,才能保证数轴上区间 [0,k][0,k] 内的每个整数坐标都至少存在一只伴舞僵尸?

Input

第一行包含两个整数 n,kn,k (1≤n≤1051 \le n \le 10^5, 0≤k≤10120 \le k \le 10^{12}),分别表示伴舞僵尸的总数和需要覆盖区间的右端点。

接下来 nn 行,每行包含两个整数 ai,bia_i,b_i (0≤ai,bi≤k0 \le a_i,b_i \le k),分别表示第 ii 只伴舞僵尸的出现时间和初始位置。

Output

输出一行一个整数,表示伴舞僵尸覆盖数轴上 [0,k][0,k] 区间内所有整数坐标所需的最短时间。

3 5
0 0
0 5
1 2
2
2 102
0 102
6 66
72

Notes

对于第一个样例,在每一秒结束时,数轴上 [0,5][0,5] 区间内各坐标的伴舞僵尸数量如下:

  • 第 00 秒:{1,0,0,0,0,1}\{1,0,0,0,0,1\};
  • 第 11 秒:{1,1,1,0,1,1}\{1,1,1,0,1,1\};
  • 第 22 秒:{2,3,2,2,2,2}\{2,3,2,2,2,2\}。

在第 22 秒时,数轴上 [0,5][0,5] 区间内的每个整数坐标处都至少存在一只伴舞僵尸。