В каком-то другом мире сегодня 30 декабря. В саду деда Коковани посажено
N деревьев. Высота
i-го дерева (1 <= i <= N) равна
hi метров. Он решает выбрать из этих деревьев
K деревьев и украсить их гирляндой. Чтобы декорации были красивее, высота украшенных деревьев должна быть как можно ближе друг к другу. Более конкретно, пусть высота самого высокого украшенного дерева будет
hmax метров, а высота самого низкого декорированного дерева будет
hmin метров. Чем меньше значение
hmax-hmin, тем лучше. Определите минимально возможное значение
hmax-hmin?
Входные данные
В первой строке записаны через пробел два числа
N и
K (2 <= N, K <= 10
5). В следующих
N строках записаны целые числа
hi (1 <= h
i <= 10
9), по одному в строке.
Выходные данные
Выведите на экран ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5 3
10
15
11
14
12 |
2 |
Если украсить первое, третье и пятое деревья, hmax=12, hmin=10, hmax-hmin=2. |
| 2 |
5 3
5
7
5
7
7 |
0 |
|