Низька потужність
Ви проектуєте продвинуті чіпи для обчислювальних машин. Виробництво чіпів просте і поставлено на рейки, проте проблему викликають джерела живлення, так як доступні батареї мають різні вихідні потужності.
Уявіть, що у нас є 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.