圣诞夜

题目描述

在某个世界,今天是圣诞夜。

高羽先生的庭院里种着 $N$ 棵树。第 $i$ 棵树 $(1 \leq i \leq N)$ 的高度是 $h_i$ 米。

他决定从这些树中选出 $K$ 棵进行灯饰装饰。为了创造更美的景象,他想装饰高度尽量接近的树。

更具体地说,设装饰的树中最高的高度为 $h_{max}$ 米,最矮的高度为 $h_{min}$ 米,则 $h_{max} - h_{min}$ 越小越好。$h_{max} - h_{min}$ 最小能是多少?

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$h_1$
$h_2$
$:$
$h_N$

输出格式

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

样例

5 3
10
15
11
14
12

2

装饰第 $1, 3, 5$ 棵树时,有 $h_{max} = 12, h_{min} = 10$,$h_{max} - h_{min} = 2$,这是最优的。

5 3
5
7
5
7
7

0

装饰第 $2, 4, 5$ 棵树时,有 $h_{max} = 7, h_{min} = 7$,$h_{max} - h_{min} = 0$,这是最优的。

这些输入样例中树的数量不算多,但请注意最多可能有 $10$ 万棵树(这里不可能贴上 $10$ 万行的输入样例)。

数据范围

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