[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$。

输入输出格式

输入格式


第一行 $2$ 个整数 $N$ 和 $D$。 接下来 $N$ 行每行 $2$ 个整数,表示水滴的坐标 $(x,y)$。

输出格式


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

输入输出样例

输入样例 #1

4 5
6 3
2 4
4 10
12 15

输出样例 #1

2

说明

有 $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$ 。