День святого Валентина#10

День святого Валентина

1 секунда
256 мегабайтів
Середня

Скоро день святого Валентина і, Степану як великому прихильнику даного свята, доручили вибрати кульки для прикраси зали.

Профорг університету, де навчається Степан, веде строгий перелік усіх кульок, згідно якому в наявності є однокольорових (що поробиш – бідні студенти) кульок, діаметр -ї кульки (1 \le i \le N) дорівнює D_i міліметрів. Згідно новим вимогам профкому, залу необхідно прикрасити не менше чим кульками. Оскільки профоргу університету не подобається свято закоханих, то вона ввела своє поняття – так званий показник некрасивості – рівний максимально можливому числу D_i - D_j при 1 \le i, j \le M, де – кількість кульок для зали, а D_i – їх діаметр.

Допоможіть Степану із іграшок вибрати (M \ge K) так, щоб для вибраних кульок показник некрасивості був мінімальним.

Вхідні дані

Перший рядок вхідного файлу містить два натуральних числа (2 \le N \le 100\,000) і (2 \le K \le N) відповідно.

Другий рядок містить цілих чисел D_i (1 \le D_i \le 10^9) – діаметр -ї кульки.

Вихідні дані

Вихідний файл має містити значення показника некрасивості вибраних кульок.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

Існує кілька різних варіантів вибору. Степан може вибрати, наприклад, 6 кульок: 3, 5, 6, 4, 7 і 8.

Степан вибере 4 кульки: 1, 5, 3 і 6.