Socks
TopCoder TCO2016 Round 1A
Time Limit: 0.1s, Memory Limit: 64MiB
До момента, в който програмист се класира на финал на TopCoder Open той или тя все трябва поне да е чувал(а) за митичното устройство, наречено "пералня". Интересен факт за това устройство е, че то не се захранва с електричество, както повечето от вас сигурно си мислят, ами с чорапи.

Ели от известно време живее без родителите си. Всеки път, когато тя пере дрехите си, някои от нейните чорапи мистериозно изчезват. В следствие на това момичето е събрало завиден брой единични чорапи с различни размери.

Сега тя иска да комбинира някои от тях в чифтове, потенциално използвайки чорапи с различни размери като чифт (нали не вярвате, че някой ще забележи, ако носите чорап 36-ти размер на левия крак и 37-ми на десния?). Ели иска да направи P чифта от N-те чорапа, които има. Всеки два чорапа могат да бъдат комбинирани в чифт, но все пак Ели не обича единият да е много по-голям от другия. Затова, тя е решила да ги комбинира по такъв начин, че най-голямата разлика между размер на чорапи в един чифт да е възможно най-малка.

По дадени размерите на наличните чорапи и броя чифтове, които момичето иска да направи, можете ли да определите каква ще е разликата в размерите на чорапите в най-лошия чифт?
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и P – съответно броя единични чорапи и броя чифтове, които момичето иска да направи. На следващия ред ще бъдат зададени N цели числа A1, A2, ..., AN, разделени с интервали – размерите на наличните чорапи.
Изход
На стандартния изход изведете едно цяло число – минималната възможна разлика в размерите на чорапите в най-лошата двойка.
Ограничения
  • 2 ≤ N ≤ 100,000
  • 1 ≤ PN / 2
  • 1 ≤ Ai ≤ 1,000,000,000
Примерен Вход Примерен Изход
6 2 42 37 84 36 41 42 1
14 7 17 3 13 3 2 17 11 5 5 7 11 7 13 19 4
10 3 177 169 170 191 188 185 177 193 179 175 2
В първия пример Ели има 6 чорапа и иска от тях да направи 2 чифта. Едно от възможните оптимални съчетания е да събере тези с размери 36 и 37 в един чифт и тези с размери 42 и 42 в друг. Максималната разлика е 1 (|36-37|).
Мрън!