Задача G. Хештег рыжих

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Союзу рыжих нужен новый представитель! Объявление об этом событии опубликовано на первой полосе газеты "Times". Каждый соискатель отправляет по электронной почте своё резюме с фотографией и ждёт результата.

Всего фирма получила n писем-заявок. Для более тщательного отбора решено пригласить на собеседование не менее k человек. Естественно, они должны быть как можно более рыжими.

Цвет волос каждого кандидата определяется по фотографии в формате цвета HTML в виде символа "хештег" и трёх пар шестнадцатеричных цифр, где каждая пара отвечает за свой цвет: две первые цифры — красный, две в середине — зелёный и две последние цифры — синий. Например, абсолютный блондин будет записан как #FFFFFF, брюнет — как #000000, серый цвет волос будет закодирован как #808080 и так далее. Чистый рыжий цвет, взятый за образец, имеет формат #D77D31.

Для определения того, насколько близок цвет волос кандидата к образцу, используется Манхэттенское расстояние — сумма модулей разностей соответствующих значений. Например, для блондина этот параметр окажется равен |D716 − FF16| + |7D16 − FF16| + |3116 − FF16| = 40 + 130 + 206 = 376, для брюнета |D716 − 0016| + |7D16 − 0016| + |3116 − 0016| = 215 + 125 + 49 = 389, для сероволосого — 169, для почти рыжего #D57A39 — 13, для образцово рыжего — нулю.

Помогите Союзу рыжих определить наименьшее значение параметра, достаточное для приглашения на собеседование не менее k кандидатов из n с наиболее близким к образцу цветом волос.

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и k. В следующих n строках расположены описания цвета волос кандидатов в формате цвета HTML. Гарантируется, что для описания цвета в коде используются лишь шестнадцатеричные цифры (используются заглавные буквы латинского алфавита).

Формат выходных данных

Выведите одно неотрицательное целое число — минимальное значение параметра, которому будут соответствовать не менее k кандидатов из n.

Ограничения

1 ≤ k ≤ n ≤ 105

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере имеется шесть кандидатов, из которых нужно выбрать трёх "наиболее рыжих". Этот параметр для первого кандидата будет равен 376, для второго — 389, третьего — 169, четвертого — 307, пятого — 297, шестого — 274. Таким образом, значения 297 достаточно для приглашения на собеседование трёх соискателей (третьего, пятого и шестого).

Примеры тестов

Стандартный вход Стандартный выход
1
6 3
#FFFFFF
#000000
#808080
#123456
#9ABCDE
#DDDDDD
297

0.073s 0.016s 15