На сборы по программированию пригласили
N учащихся. Вечерний досуг было решено провести в виде эстафеты. Для проведения эстафеты необходимо разбить всех учащихся на
R команд по
С человек в каждой. По мнению руководителя сборов, команда будет тем успешнее на эстафете, чем менее будет различаться рост учащихся в одной команде.
Числом неуспешности команды будем называть разность между ростом самого высокого и ростом самого низкого членов этой команды (если в команде только один человек, то эта разница равна 0).
Вожатые решили сформировать команды так, чтобы максимальное из чисел неуспешности сформированных команд было минимально. Пока вожатые заняты расселением учащихся по домикам, помогите им и вычислите наименьше возможное значение максимального числа неуспешности сформированных команд.
Рассмотрим следующий пример. Пусть на сборах 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две команды по три человека в каждой. Тогда одним из вариантов является такой:
1 команда: учащиеся с ростом 225, 205, 225
2 команда: учащиеся с ростом 160, 190, 170
При этом число неуспешности первой команды будет равно 20, а число неуспешности второй — 30. Максимальное из чисел неуспешности будет 30, и это будет наилучший возможный результат.
Входные данные
Первая строка входных данных содержит три натуральных числа
N,
R и
C - количество учащихся на сборах, количество команд и количество человек в каждой команды (1 <= R·C <= N <= 100 000).
Далее вводятся
N целых чисел — рост каждого из
N учеников. Рост ученика - натуральное число, не превышающее 1 000 000 000.
Выходные данные
Выведите одно число - наименьше возможное значение максимального числа неуспешности сформированных команд.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8 2 3
170
205
225
190
260
130
225
160
|
30
|