3882: 愤怒的小鸟(angry)

angry.in/out

小G设计了一款热门游戏“愤怒的小鸟”。这完全是小G原创，游戏规则是这样：玩家用弹弓弹射一只小鸟，目标是前方一排位于数字线上不同点的爆炸珠; 小鸟以能量R撞击爆炸珠后能产生足够的能量使爆炸珠爆炸， 爆炸珠爆炸后又会造成连锁反应，继续引爆R范围内的爆炸珠，游戏的任务是用一系列愤怒的小鸟引爆所有的爆炸珠。

有N个位于一行不同整数位置x1,x2,...,xN的爆炸珠，如果一只小鸟以能量R撞击了位于x位置的爆炸珠，那么会引起半径为R（x-R到x+R)的连环爆炸，并摧毁范围内的所有的爆炸珠

一共有K只小鸟被用来作为炮弹，每只小鸟的能量R都相同。请帮忙决定这个最小的能量，使得用这K只小鸟可以摧毁所有的爆炸珠。

【数据范围】

1<=N<=50,000，1<=K<=10

第一行包含两个整数N,K

解析来N行，每行包含一个整数xi,表示每个爆炸珠的位置(0<=xi<=1,000,000,000)

7 2
20
25
18
8
10
3
1

5