[Usaco2016 Jan]Angry Cows

时间限制:1s      空间限制:128MB

题目描述

奶牛Bessie设计了一个游戏:“愤怒的奶牛”。游戏的原型是:有一些可爆炸的草堆分布在一条数轴的某些坐标上,玩家用弹弓把一头奶牛发射到数轴上。奶牛砸到数轴上的冲击波会引发附近的草堆爆炸。游戏的目标是玩家用一些奶牛炸掉所有的草堆。 
有N个草堆在数轴的不同位置,坐标为x1,x2,….,xn。如果玩家以能量R把奶牛发射到坐标x,就会引爆半径R及以内的的草堆,即坐标范围[x−R,x+R]的草堆都会燃爆。 
现在有K头奶牛,每头奶牛的能量都是R,请计算如果要引爆所有的草堆,最小的R是多少? 


输入格式

第一行:2个整数N(1≤N≤50,000)和K(1≤K≤10)。 
下面有N行,每行一个整数:x1,x2,…,xn,范围在[0…1,000,000,000]。 


输出格式

输出最小可能的R。


样例输入

7 2
20
25
18
8
10
3
1

样例输出

5

提示

没有写明提示


题目来源

Silver

Menuappsclose