Задача 4C. Выборы смотрителя

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

Условие

В Убежище №13 скоро выборы! Старый смотритель ушел на покой и теперь любой житель может зарегистрироваться в кандидаты на ответственную должность. После этого все остальные избиратели оценивают кандидата и после выборов либо назначают его новым смотрителем, либо нет (в этом случае выдвигается другой кандидат). В отличие от других Убежищ Волт-Тек, здесь выбирают исключительно харизматичных лидеров.

Харизматичность — категория непростая... Она делится на три составляющих, а они, в свою очередь, на три параметра каждая (схема ниже на рисунке). Каждый житель Убежища либо обладает определенным параметром, либо нет, соответственно, харизматичность каждого жителя можно описать девятизначным двоичным числом.

Каждый житель убежища имеет свои представления о харизматичности (она не обязана совпадать с его внешним видом). Кому-то по душе строгий довоенный костюм, а кому-то — родной комбинезон убежища с числом 13 на спине. Кто-то считает, что будущий смотритель должен быть серьезным, а кто-то — весёлым. Одни считают, что без хорошей прически лидер — не лидер, а другие — что "шрамы украшают мужчин". Что поделать, сколько людей — столько и мнений... Важно только то, что во время выборов каждый житель оценивает харизматичность кандидата, и если все параметры ему нравятся, кандидат получает голос "За", а если хотя бы один параметр отличается — "Против". Если голосов "За" окажется больше определенного заранее числа — кандидат становится новым смотрителем.

Один из жителей убежища (назовем его Джон) решил подойти к выборам серьезно. Он побеседовал с каждым избирателем и записал его представления об идеальном смотрителе сначала в виде девятизначного двоичного числа, а потом перевел его в более привычное десятичное представление. Свою внешность Джон тоже записал с помощью такого представления, после чего почесал в затылке. Полных совпадений было маловато...

К счастью, Джон скопил немного крышек и в состоянии изменить в своей харизматичности до трех параметров (например, купить новый костюм, удалить авто-доком татуировки и оплатить услуги Тома-Весельчака для вставки в предвыборную речь удачных шуток). Подскажите, какие параметры следуют изменить Джону, чтобы как можно большее количество жителей убежища проголосовало за него? Сколько голосов удастся набрать Джону прежде чем новый смотритель отправит его за в Пустошь за водяным чипом?

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

Первая строка входного файла содержит два неотрицательных целых числа, записанных через пробел: n — количество избирателей и d — харизматичность Джона. Во второй строке через пробел записаны n чисел ai в порядке неубывания — представления об идеальном смотрителе всех избирателей.

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

В единственной строке выведите одно неотрицательное целое число — наибольшее количество голосов "За", которые сможет набрать Джон, изменив в своей харизматичности не более трех параметров.

Ограничения

1 ≤ n ≤ 100000.

0 ≤ d, ai ≤ 511.

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

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

Решения, верно работающие при 1 ≤ n ≤ 10, получат не менее 20 баллов.

Решения, верно работающие при 1 ≤ n ≤ 1000, получат не менее 60 баллов.

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

В первом примере Джон (его харизматичность соответствует двоичной записи 000000100) может изменить два параметра и будет соответствовать идеальным представлениям трех избирателей (4410 = 0001011002). Получить четыре голоса (9710 = 0011000012) он не сможет — необходимо менять четыре параметра.

Во втором примере никакие ухищрения Джона (9710 = 1111111112) не позволят ему набрать даже один голос.

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

Стандартный вход Стандартный выход
1
10 4
5 13 13 44 44 44 97 97 97 97
3
2
10 255
5 13 13 44 44 44 97 97 97 97
0

0.105s 0.011s 15