编故事
题号:NC216129
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

SMU的校赛又要开始了,HL却为出题犯愁,为什么呢?因为题目要套在一个故事里,至少HL是这么想的,因为他觉得这样题目才显得有逼格,嘻嘻,可是HL并不善于编故事。最后,他想破脑袋,于是遍了这样一个故事:

很久很久以前,有一个古老的王国,这个王国里有n户人家,国王是个很喜欢团结的人,他总是喜欢让他的子民们举行一些活动,来使他们促进团结。这天,他在巡视国家时,发现街上的人走路迈出的步子大小可能不一样。他灵感一现,想到了一个非常有意思且能促进团结的游戏,“两人三足”!!!但是国王喜欢团结,所以他并不想让他的子民分组决出胜负,而是要求每家每户都派出一个人,然后让所有人排成一排,组成一个“mm+1足”。只要他们能顺利走完一定的路程,国王就会很高兴,然后就会开国库,发粮食!子民很当然很想得到粮食啊,但是他们陷入了困惑,因为每个人的迈出的步子大小是固定的,没法缩小或增大,而且只要有两个人的步子大小差值超过k,那么他们就会集体摔倒,游戏失败。现在他们求助于你,把每家每户的人的步子大小告诉你,让你帮他们确认他们是否可能完成游戏。为什么求助于你呢?因为在这个故事里,你就是他们国家隔壁山上正在修炼的程序员!(滑稽)

两人三足的游戏规则:由两个人团结协作,两人并排站立,一人左腿与另一人右腿的膝盖以下,脚踝以上部分用绳子绑上 比赛在起点处开始出发,至对面标志处折回,返回至起点处,再将绳子解后,交给下一组队员进行比赛,最后以完成时间长短进行排名。

——复制自百度百科

输入描述:

第一行两个整数n和k,n(1 <= n <= 100000),表示王国有多少户人家,k(1 <= k <= 1000000000),表示最大步子和步子差值超过k就会集体摔倒;接下来n行,每行5个整数a(1 <= a <= 1000000000),第i个整数代表这户人家第i个人步子的大小。

输出描述:

输出包含一行,若子民们能完成游戏,输出所有可行方案中的最大步子和最小步子的差值的最小值;若不可能完成游戏,输出-1。

 

示例1

输入

复制
4 2
1 2 3 4 5
3 4 6 3 4
3 4 5 6 7
7 1 8 6 11

输出

复制
1
示例2

输入

复制
3 4
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

输出

复制
-1