Низкая мощность
Вы проектируете продвинутые чипы для вычислительных машин. Производство чипов просто и поставлено на рельсы, однако проблему вызывают источники питания, так как доступные батареи имеют различные выходные мощности.
Представьте, что у нас есть n машин с двумя чипами на каждой, а каждый чип питается от k батарей. Удивительно, но не имеет значения, сколько энергии потребляют чипы, однако важно, чтобы выходные мощности чипов как можно меньше отличались друг от друга, так как в этом случае машина работает наилучшим образом. Выходная мощность чипа — это минимальная выходная мощность среди всех k батарей в чипе.
Вы располагаете 2nk батареями, которые вам необходимо распределить по чипам машин. Может оказаться, что нет способа распределить батареи так, чтобы выходные мощности чипов были равны для всех машин. Тем не менее, вам нужно минимизировать разность мощностей. То есть Вы хотите гарантировать вашим заказчикам, что разность выходных мощностей чипов во всех машинах не превосходит d, при этом стараясь минимизировать d. Для этого вам нужно найти оптимальное распределение батарей по чипам.
Рассмотрим пример 1. Имеются 2 машины, каждая из которых требует 3 батареи для чипа, а выходные мощности батарей равны 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Можно, например, батареями с мощностями 1, 3, 5 питать первый чип, батареями с мощностями 2, 4, 12 питать второй чип той же машины, батареями с мощностями 6, 8, 9 - третий чип, а батареями с мощностями 7, 10, 11 - четвертый. Выходные мощности чипов соответственно равны 1, 2, 6 и 7, а разница между выходами мощностей равна 1 в обеих машинах. Отметим, что этого результата можно добиться и другими способами.
Входные данные
Входные данные состоят из одного теста, содержащего две строки. В первой строке заданы два натуральных числа: количество машин n и количество батарей на чипе k (2nk ≤ 10^6). Вторая строка содержит 2nk чисел p_i (1 ≤ p_i ≤ 10^9), описывающие выходные мощности батарей.
Выходные данные
Выведите минимальное d такое, что существует распределение батарей по чипам, чтобы разность выходных мощностей чипов в каждой машине не превосходила d.