4521 - Flowerpot

老板需要你帮忙浇花。给出 N 滴水的坐标，(x,y) 表示水滴最初的坐标。

每滴水均以每秒 1 个单位长度的速度下落。你需要把花盆放在 x 轴上的某个位置，使得花盆接到第 1 滴水与最后 1 滴水之间的时间差至少为 D。

如果水滴落在 x 轴上的位置与花盆的边沿对齐，也认为被接住。

给出 N 滴水的坐标和时间差 D ，请算出最小的花盆宽度 W。

第一行 2 个整数 N 和 D。

接下来 N 行，每行 2 个整数，表示水滴的坐标 (x,y)。

一行 1 个整数，表示最小的花盆宽度。如果无法构造出满足题意的花盆，则输出 -1。

【样例解释】

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

【数据范围】

40\% 的数据：1 \le N \le 1000 ，1 \le D \le 2000。

100\% 的数据：1 \le N \le 10 ^ 5，1 \le D \le 10 ^ 6，0\le x,y\le10^6。

USACO