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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ k ≤ n ≤ 10⁵

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

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

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

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

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

6 3
#FFFFFF
#000000
#808080
#123456
#9ABCDE
#DDDDDD

297