C - 圣诞夜

得分：300 分

问题描述

在另一个世界，今天是圣诞夜。

在 Takaha 先生的花园里种了 $N$ 棵树。第 $i$ 棵树（$1 \leq i \leq N$）的高度为 $h_i$ 米。

他决定从这些树中选出 $K$ 棵树，并用电灯装饰它们。为了使风景更加美丽，装饰的树的高度应该尽可能接近。

具体来说，设最高装饰树的高度为 $h_{max}$ 米，最矮装饰树的高度为 $h_{min}$ 米。$h_{max} - h_{min}$ 的值越小，越好。$h_{max} - h_{min}$ 的最小可能值是多少？

约束

• $2 \leq K < N \leq 10^5$
• $1 \leq h_i \leq 10^9$
• $h_i$ 是整数。

输入

从标准输入获得输入数据的格式如下：

$N$ $K$

$h_1$

$h_2$

$:$

$h_N$

输出

输出 $h_{max} - h_{min}$ 的最小可能值。

5 3
10
15
11
14
12

2

如果我们装饰第一、第三和第五棵树，$h_{max} = 12$，$h_{min} = 10$，因此 $h_{max} - h_{min} = 2$。这是最优的。

5 3
5
7
5
7
7

0

如果我们装饰第二、第四和第五棵树，$h_{max} = 7$，$h_{min} = 7$，因此 $h_{max} - h_{min} = 0$。这是最优的。

在这些样例输入中，树木数量并不多，但请注意，树木数量最多可达十万棵（我们无法在这里输入一百万行的样例）。