eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 0.5 seconds
Memory limit 128 MiB

Скоро день святого Валентина и Степану, как большому поклоннику этого праздника, поручили выбрать шарики для украшения зала. Профорг университета, где учится Степан, ведёт строгий учёт всех шариков, согласно которому в наличии имеется N одноцветных (що сделаешь – бедные студенты) шариков, диаметр i-го шарика (1iN) равен D_i миллиметров. Согласно новых требований профкома, зал необходимо украсить не менее чем K шариками. Так как профоргу университета не нравится праздник влюблённых, то она ввела своё понятие (термин) – так называемый показатель некрасивости – он равен максимально возможному числу D_i–D_j при 1i, jM, где M – количество шариков для зала, а D_i – их диаметр.

Помогите Степану из N игрушек выбрать М (MK) так, чтобы для выбранных M шариков показатель некрасивости был минимален.

Input data

Первая строка входного файла содержит два натуральных числа N (2N100000) и K (2KN) соответственно. Вторая строка одержит N целых чисел D_i (1D_i10^9) – диаметр i-го шарика.

Output data

Выходной файл должен содержать значение показателя некрасивости выбранных M шариков.

Examples

Input example #1
8 5
10 20 10 20 10 10 20 20
Output example #1
10
Source III этап Всеукраинской олимпиады школьников 2012-2013, 1 тур