程序设计能力实训

1238. 星巴克连锁店

单点时限: 2.0 sec

内存限制: 256 MB

jxtxzzw喜欢喝星巴克。

上海有很多地铁。

jxtxzzw想要建立上海地铁沿线的星巴克连锁店,现在要在一条铁路线的所有车站里,选择一部分车站,这些车站里面需要开设星巴克门店。

为了简化问题,我们假设上海地铁某号线为一条直线。

其中每个站点的坐标为

jxtxzzw一共要开办个星巴克连锁店,并且不希望连锁店离得太近,以使得整体的收益最大化。

jxtxzzw希望星巴克连锁店之间的最近距离尽可能大。

你能帮他算出这个最大的最近距离吗?

(断句没问题?没错。最大的·最近距离。)

输入格式

第一行输入用空格分隔的两个整数 ,分别表示车站数量和连锁店数量。

接下来一共行,每行一个整数

输出格式

输出一行整数,表示最大的最近距离。

样例

Input
6 3
1
3
5
2
7
9
Output
4
Input
5 4
5
7
10
28
9
Output
2

提示

样例说明,一共有种选择方案。

  • 5 7 9 10,最近距离为
  • 5 7 9 28,最近距离为
  • 5 7 10 28,最近距离为
  • 7 9 10 28,最近距离为
  • 5 9 10 28,最近距离为

因此,最大的最近距离为

不限期开放

题目列表