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

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

1 second
256 megabytes
Medium

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

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

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

Input

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

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

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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

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