/ WHOJ / 题库 /

空投炮兵

空投炮兵

描述

19161916年德军两名士兵携带炸药从飞机机翼上跳下破坏沙皇俄国后方的铁路,空降兵这一兵种就极大地改变了战争的形态。空降兵具有极强的机动性,在战斗机群的掩护下,几乎可以在战场的任意位置甚至战场的后方投送兵力。
现在作为一名足智多谋的参谋,你需要安排一次空降来摧毁敌人的若干火车站。敌人的铁路可以看成一条直线,在这条直线上的NN 个点处建有敌人的火车站。将有K K支炮兵小队被空降。一支炮兵小队配有一门有效射程为RR 的火炮,如果该小队被空降到位置xx 处,那么所有xRx-Rx+Rx+R 之间的火车站都可以被这支炮兵小队摧毁。
现在考虑到R R越大空投的难度越大,军长希望尽可能使RR 更小,于是他找到了你,希望你能告诉他R R最小取多少,可以保证所有的敌人火车站都被摧毁。由于你的空军十分强大,因此你可以在这条铁路上的任意位置空降炮兵小队。

格式

输入格式

第一行包含两个整数NN KK
接下来N N行,每行一个整数X[i]X[i] 表示第ii 个火车站所处的位置。

输出格式

包含一个整数表示在摧毁敌人所有火车站的前提下最小的RR

样例1

输入样例1

7 2
20
25
18
8
10
3
1

输出样例1

限制

100%100\%的数据:N50000K100X[i]109N≤50000,K≤10,0≤X[i]≤10^9