题目描述

农场主约翰一直很难让他的植物生长，需要你的帮助来给它们适当浇水。我们给出了二维平面上N个雨滴（1<=N<=100000）的位置，其中y代表雨滴的垂直高度，x代表雨滴在水平线上的位置：

每个液滴以每秒1个单位的速率向下（朝向X轴）。你想把农夫约翰的花盆宽W沿X轴放置在某个地方，这样第一个雨滴撞击花盆和最后一个雨滴撞击花盆的时间差至少是一定量D（这样花盆中的花能接受足够的水）。一滴落在花盆边缘的水就等于碰到了花盆。
给定D值和N个雨滴的位置，请计算w的最小可能值。

输入格式：

第一行2个整数 N 和 D。
第2.. N+1行每行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..6的位置，它可以接到1和3水滴, 之间的时间差为10-3 = 7满足条件。

数据范围

40%的数据：1 ≤ N ≤ 1000，1 ≤ D ≤ 2000；
100%的数据：1 ≤ N ≤ 100000，1 ≤ D ≤ 1000000，0≤x,y≤10^6。