4207: 花盆（fpot）

【问题描述】

FJ一直苦于无法让他的植物生长，需要你的帮助给植物适当地浇水。现在给你2D平面上N个雨水落下的位置 (1 <= N <= 100,000)，y代表雨水落下的垂直高度，x代表横向坐标：

每一滴雨水朝着X轴方向以每秒1个单位的速度下落。FJ想要把宽度为W的花盆沿着X轴移动到某个位置，以保证第一滴雨水落入花盆的时间和最后一滴雨水落入花盆的时间的差至少是D，（这样就能让花盆里的花获得大量的雨水）砸到花盆边缘的雨水也视为落入了花盆。

给出D的值以及N滴雨水的位置，请计算出W的最小值。

【输入格式】

第1行：两个用空格隔开的整数N 和D. (1 <= D <= 1,000,000)

第2..N+1行: 第 i+1 行(xi,yi)表示雨点i的初始位置 (0<=xi, yi<=1,000,000)

【输出格式】

一个整数，表示最小的花盆宽度。如果找不到这个方案，输出“-1”。

【输入样例】

4 5

6 3

2 4

4 10

12 15

【输出样例】

2

样例解释:

一个宽度w为2的花盆，如果放在x=4..6，那么它可以接到第1，第3滴雨水，总共间隔为10-3=7，满足>=5。