小田的花盆

题目描述

小田在给他的植物设计花盆时遇到了麻烦，需要你的帮助来让它们能适当地获得水分。

小田的植物园会通过降下雨滴来给植物浇水，现在你获得了某一时刻 $n$ 个雨滴在 2维平面 中的坐标，$x$ 表示该雨滴下落到 $x$ 轴的位置，$y$ 表示雨滴的高度。

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

我们认为，只要水滴落在 $x$ 轴上，与花盆的边沿对齐，就认为它是被接住的。现在告诉你 $n$ 滴水滴的坐标和 $d$ 的大小，请你计算出最小的花盆宽度 $W$。

输入描述

第一行输入两个整数 $n,D$。

接下来 $n$ 行，每行输入两个数字 $x_{i}, y_{i}$ ，表示第 $i$ 滴雨滴的坐标。

输出描述

输出包含一行一个整数，表示最终的答案。

如果无法构造出足够宽的花盆来满足要求，则输出 $-1$。

输入输出样例

输入 #1

4 5
6 3
2 4
4 10
12 15

输出 #1

2

说明/提示

【样例 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$ 。