Кубок Томска по программированию 2013

Соревнование завершилось 26.05.13 в 15:55

A. Распределение воздушных шаров

Автор задачи: Хаустов Павел
Источник: Кубок Томска 2013
Ограничение по времени: 2 с.
Ограничение по памяти: 256 МБ

В ходе подготовки «Кубка Томска по программированию 2018» возникла небольшая трудность.

За каждую решенную задачу планируется приклеивать воздушный шарик к столу команды, которая ее решила. Каждой задаче должен соответствовать шарик одного определенного цвета. Никаким двум задачам не должен соответствовать шарик одного и того же цвета.

Оргкомитет подготовил восемь задач, каждой из которых соответствует уникальная буква латинского алфавита от «A» до «H». В магазине, где планируется закупать шарики, имеются шарики ровно восьми различных цветов. Известна стоимость одного шарика каждого из цветов.

В Томске имеется N команд олимпиадных программистов. Для каждой из которых организаторам известен набор задач, которые они могут решить. Организаторы такого уровня никогда не ошибаются. Поэтому если какой-то задачи нет в наборе какой-либо команды, то эта команда точно не решит ее на соревновании.

Организаторы понимают, что бюджет олимпиады составляет всего лишь S рублей, и его может не хватить для того, чтобы купить столько шариков, сколько нужно. Поэтому, возможно, придется пригласить лишь некоторые из N команд. Причем организаторы хотят купить такой набор шариков, чтобы даже если все приглашенные команды решат все задачи, которые они могут решить, закупленных шариков все равно хватит.

Перед организаторами стоит непростая задача — распределить цвета шариков по задачам и пригласить некоторые команды так, чтобы уложиться в имеющийся бюджет и при этом пригласить как можно больше команд.

Ваша задача — написать программу, которая поможет определить максимальное возможное количество приглашенных команд.

Входные данные

Первая строка содержит два целых числа N и S — количество команд в Томске и размер бюджета олимпиады (1 \leqslant N \leqslant 10^{5}, 1 \leqslant S \leqslant 10^{9}). Во второй строке содержится восемь целых чисел от 0 до 10^{4} — стоимости шариков различных цветов в магазине. Далее следует N строк, каждая из которых задает набор задач, которые может решить очередная команда. Каждая такая строка состоит из заглавных букв латинского алфавита. Буквы могут быть в произвольном порядке. Никакая буква не встречается более одного раза для одной команды.

Выходные данные

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

Примеры
Стандартный вводСтандартный вывод
5 13
1 2 3 4 5 6 7 8
AGE
AGH
AG
AE
ABCD
3
Пояснения к примерам

В приведенном примере следует пригласить первую, третью и четвертую команды, за задачу «A» давать шарик стоимости 1, за задачу «G» — стоимости 2, а за задачу «E» — стоимости 3.


В условии сказано, что A[i] не равно i. Это не так. Вычеркните это из своих условий.


Требуется рассматривать только пары автобусов, между которыми не приезжали другие автобусы с тем же номером.


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