Задача №1630. Субботник
В классе учатся N человек. Классный руководитель получил указание разбить их на R бригад по С человек в каждой и направить на субботник (N = R∙C).
Все бригады на субботнике будут заниматься переноской бревен. Каждое бревно одновременно несут все члены одной бригады. При этом бревно нести тем удобнее, чем менее различается рост членов этой бригады.
Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!
Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по четыре человека в каждой. Тогда одним из вариантов является такой:
1 бригада: люди с ростом 225, 205, 225, 260
2 бригада: люди с ростом 160, 190, 170, 130
При этом максимальное число неудобства будет во второй бригаде, оно будет равно 60, и это наилучший возможный результат.
Формат входных данных:
Сначала вводятся натуральные числа R и C количество бригад и количество человек в каждой бригаде (1 ≤ R∙C ≤ 1000). Далее вводятся N = R∙C целых чисел по одному в строке — рост каждого из N учеников. Рост ученика — натуральное число, не превышающее 1 000 000 000.
Формат выходных данных:
Выведите одно число — наименьше возможное значение максимального числа неудобства сформированных бригад.
Пример
| Входные данные | Выходные данные |
2 4 170 205 225 190 260 130 225 160 | 60 |