题目描述

老板需要你帮忙浇花。给出 N 滴水的坐标，y 表示水滴的高度，x 表示它下落到 x 轴的位置。

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

我们认为，只要水滴落到 x 轴上，与花盆的边沿对齐，就认为被接住。给出 N 滴水的坐标和 D 的大小，请算出最小的花盆的宽度 W。

输入格式

第一行 $2$ 个整数 $N$ 和 $D$。

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

输出格式

一行 $1$ 个整数，表示最小的花盆宽度。如果无法构造出满足题意的花盆，则输出 $-1$。

4 5
6 3
2 4
4 10
12 15

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 \le 10^6$。