该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

老板需要你帮忙浇花。给出${N}$滴水的坐标，${y}$表示水滴的高度，${x}$表示下落到${x}$轴的位置。

每滴水以每秒${1}$个单位长度的速度下落。你需要把花盆放在${x}$轴上的某个位置，使得从被花盆接着的第${1}$滴水开始，到被花盆接着的最后${1}$滴水结束，之间的时间差至少为${D}$，老板并不关心接到了几滴水。

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

输入格式

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

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

输出格式

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

样例

输入样例

4 5
6 3
2 4
4 10
12 15

输出样例

2

提示

样例解释

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

数据范围

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

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