P2698 [USACO12MAR] Flowerpot S

Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of $N$ raindrops $(1 \leq N \leq 100,000)$ in the 2D plane, where $y$ represents vertical height of the drop, and $x$ represents its location over a 1D number line:  Each drop falls downward (towards the $x$ axis) at a rate of $1$ unit per second. You would like to place Farmer John's flowerpot of width $W$ somewhere along the $x$ axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount $D$ (so that the flowers in the pot receive plenty of water). A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot. Given the value of $D$ and the locations of the $N$ raindrops, please compute the minimum possible value of $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$。