# [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 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line: ![](https://cdn.luogu.com.cn/upload/pic/9174.png) 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. 老板需要你帮忙浇花。给出 \$N\$ 滴水的坐标，\$y\$ 表示水滴的高度，\$x\$ 表示它下落到 \$x\$ 轴的位置。 每滴水以每秒 \$1\$ 个单位长度的速度下落。你需要把花盆放在 \$x\$ 轴上的某个位置，使得从被花盆接着的第 \$1\$ 滴水开始，到被花盆接着的最后 \$1\$ 滴水结束，之间的时间差至少为 \$D\$。 我们认为，只要水滴落到 \$x\$ 轴上，与花盆的边沿对齐，就认为被接住。给出 \$N\$ 滴水的坐标和 \$D\$ 的大小，请算出最小的花盆的宽度 \$W\$。

## 输入输出样例

### 输入样例 #1

``````4 5
6 3
2 4
4 10
12 15``````

### 输出样例 #1

``2``