← 返回题目列表

Codeforces · 883/I

I. 照片处理

中文机器翻译题面 查看原题

Evlampiy 发现了一款​​更酷的照片处理应用程序。然而该应用程序有一定的局限性。

每张照片 i 都有一个对比度 vi。为了使处理真正达到高质量,应用程序必须接收至少 k 张照片,其对比度差异尽可能小。

Evlampiy 已经知道他的 n 张照片中每张的对比度 vi。现在他想将照片分成组,使得每个组至少包含k张照片。因此,每张照片必须完全属于一个组。

他认为第j组的处理时间是该组中vi的最大值和最小值之间的差。由于多线程,分组的处理时间是所有组中的最大处理时间。

将n张照片分成组,使得划分的处理时间尽可能最小,即所有组的最大处理时间尽可能短。

输入

第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 3·105) — 照片数量和组的最小大小。

第二行包含 n 个整数 v1, v2, ..., vn (1 ≤ vi ≤ 109),其中 vi 是第 i 张照片的对比度。

输出

打印分组的最短处理时间。

示例

输入 #1

5 2
50 110 130 40 120

输出 #1

20

输入 #2

4 1
2 3 4 1

输出 #2

0

注意

在第一个示例中,照片应分为 2 组:[40, 50] 和 [110, 120, 130]。第一组的处理时间为10,第二组的处理时间为20。10和20之间最大为20。不可能将照片分组为使得分组的处理时间小于20。

在第二个示例中,照片应分为四组,每组包含一张照片。因此除法的最小可能处理时间为 0。