题目描述

老板需要你帮忙浇花。给出$\red{N}$滴水的坐标，$\red{y}$表示水滴的高度，$\red{x}$表示它下落到$\red{x}$轴的位置。 每滴水以每秒$\red{1}$个单位长度的速度下落。你需要把花盆放在$\red{x}$轴上的某个位置，使得从被花盆接着的第$\red{1}$滴水开始，到被花盆接着的最后$\red{1}$滴水结束，之间的时间差至少为$\red{D}$。

我们认为，只要水滴落到$\red{x}$轴上，与花盆的边沿对齐，就认为被接住。给出$\red{N}$滴水的坐标和$\red{D}$的大小，请算出最小的花盆的宽度$\red{W}$。

输入格式

第一行$\red{2}$个整数 $\red{N }$和 $\red{D}$。

第$\red{2.. N+1}$行每行$\red{2}$个整数，表示水滴的坐标$\red{(x,y)}$。

输出格式

仅一行$\red{1}$个整数，表示最小的花盆的宽度。如果无法构造出足够宽的花盆，使得在$\red{D}$单位的时间接住满足要求的水滴，则输出$\red{-1}$。

样例

输入样例

4 5
6 3
2 4
4 10
12 15

输出样例

2

提示

样例解释

有$\red{4}$滴水， $\red{(6,3), (2,4), (4,10), (12,15).}$水滴必须用至少$\red{5}$秒时间落入花盆。花盆的宽度为$\red{2}$是必须且足够的。把花盆放在$\red{x=4..6}$的位置，它可以接到$\red{1}$和$\red{3}$水滴, 之间的时间差为$\red{10-3 = 7}$满足条件。

数据范围

$\red{40\%}$的数据：$\red{1 ≤}$ $\red{N ≤}$ $\red{1000，}$$\red{1 ≤}$ $\red{D ≤}$ $\red{2000}$；

$\red{100\%}$的数据：$\red{1 ≤}$ $\red{N ≤}$ $\red{100000，}$$\red{1 ≤}$ $\red{D ≤}$ $\red{1000000，}$$\red{0≤}$$\red{x,y≤}$$\red{10^6}$。