1902: 浇水
内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：118
通过：41
题目描述
给出 N 滴水的坐标，y 表示水滴的高度，x 表示它下落到 x 轴的位置。
每滴水以每秒 1 个单位长度的速度下落。
你需要把花盆放在 x 轴上的某个位置，使得从被花盆接着的第 1 滴水开始，到被花盆接着的最后 1 滴水结束，之间的时间差至少为 D。
我们认为，只要水滴落到 x 轴上，与花盆的边沿对齐或者在花盆中，就认为被接住。
给出 N 滴水的坐标和 D 的大小，请算出最小的花盆的宽度 W。
输入格式
第1行：两个整数 N 和 D，1 <= N <= 100,000，1 <= D <= 1,000,000。
接下来 N 行：每行两个整数 x，y，表示雨滴的坐标，0 <= x, y <= 1,000,000。
接下来 N 行：每行两个整数 x，y，表示雨滴的坐标，0 <= x, y <= 1,000,000。
输出格式
仅一行 1 个整数，表示最小的花盆的宽度。
如果无法构造出足够宽的花盆，使得在 D 单位的时间接住满足要求的水滴，则输出 −1。
如果无法构造出足够宽的花盆，使得在 D 单位的时间接住满足要求的水滴，则输出 −1。
输入样例 复制
4 5
6 3
2 4
4 10
12 15输出样例 复制
2数据范围与提示
来源：USACO 2012.3