8408: Flowerpot

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

农夫约翰一直难以让他种植的植物茁壮成长,他需要你来给植物适当的浇水。

给定二维平面中 NN 个雨滴的位置,其中 yy 表示雨滴的垂直高度,xx 表示其在一维数轴上的位置。

fig_flowerpot.png

每个雨滴以每秒 11 个单位长度的速率向下(朝 xx 轴)下落。

你需要将宽度为 WW 的农夫约翰的花盆沿 xx 轴放置在某处,以便第一个雨滴击中花盆与最后一个雨滴击中花盆之间的时间差至少为 DD(使得花盆中的花获得充足的水)。

一滴水落在花盆的边缘就等于击中了花盆。

给定 DD 的值和 NN 个雨滴的位置,请计算 WW 的最小可能值。

输入格式

第一行包含两个整数 NN 和 DD

接下来 NN 行,每行包含两个整数 (x,y)(x,y),表示一个雨滴的位置坐标。

输出格式

输出 WW 的最小可能值。

如果无解,则输出 −1−1

输入样例 复制

4 5
6 3
2 4
4 10
12 15

输出样例 复制

2

数据范围与提示

1≤N≤100000,
1≤D≤1000000,
0≤x,y≤1000000