UOJ Logo

NOI.AC

1S 512MB

#1639. 团队协作

Statistics

题目描述

$Mas$这学期选择了一门实验课程,由于$Mas$实力很强,所以老师请他来担任助教,众所众知这门课程需求完成一个比较复杂的项目,往年老师会将同学们尽可能平均的分为几组,但是因为总有同学反映分到的队友实力不足或者差距很大,所以今年老师想请$Mas$来帮忙分配小组成员,完成本学期的项目教学目标。

现在已知每个人的项目实力,同时为了教学效果,每个小组至少需要有$k$个同学,每个同学都必须被分入某一个小组中,求如何分组,可以使得每个小组内同学的实力之差的最大值达到最小?

输入

输入第一行两个数$n,k$ 第二行为一个$n$个数的正整数序列,表示每个同学的实力值$v_i$

输出

输出一个数,表示在最优分组下,小组内实力之差最大值的最小值

输入样例

4 1
2 3 4 1

输出样例

0

数据规模

对于前$10\%$的数据,$k \leq n \leq 10$ 对于前$30\%$的数据,$k\leq n\leq 100$ 对于前$60\%$的数据,$k \leq n \leq 10000$ 对于前$100\%$的数据,$k \leq n \leq 300000,v_i \leq 10^9$