50 руководство команды «байтсбург юнайтед» после очередного поражения уволило предыдущего главного тренера. на его место был назначен бывший игрок этой команды, успешно зарекомендовавший себя в качестве тренера за рубежом. в свой тренерский штаб новый тренер пригласил в качестве аналитика специалиста по продвинутой статистике. и тот сразу же предложил новую модель внутрикомандной психологии. как известно, для взаимоотношений в команде часто используют термин «командная »; от аналитика поступило предложение записывать преобразования в структуре команды в виде своеобразных реакций. роли игроков в команде обозначили заглавными латинскими буквами: например, f3ad10a обозначает группу из трёх форвардов, вице-капитана, 10 защитников и ещё одного вице-капитана. соответственно, если требуется выбрать из этой группы наибольшее количество групп в составе вице-капитана, форварда и трёх защитников, то таких групп будет две (так как для третьей не хватит вице-капитана), то есть из группы f3ad10a можно получить две группы afd3. а вот групп fd3 можно получить целых 3. иначе говоря, суммарное количество игроков каждой роли в исходной группе не должно быть меньше суммарного числа игроков данной роли в группах, на которые происходит разбиение. на психологический тренинг пришли несколько одинаково структурированных групп игроков. вам задан тип исходной группы игроков, количество этих групп и тип команды, требуемый для психологических тренингов. ваша — найти максимальное количество команд, на которое можно разделить пришедших на занятия игроков. формат ввода первая строка входных данных содержит структуру группы — непустую строку s длиной не более 2500 символов, и количество входных групп n ( 1 ≤ n ≤ 1 0 3 ). строка состоит из заглавных латинских букв и цифр. после каждой буквы может стоять не более трёх цифр, первой цифрой после буквы не может быть 0. число, записанное после буквы, обозначает количество игроков соответствующей роли в группе. если число опущено (сразу после буквы идёт другая буква), то считается, что соответствующее число равно 1 (при этом явное указание единицы тоже возможно. вторая строка задаёт структуру команды для тренинга в аналогичном формате. формат вывода выведите одно число — максимальное количество команд для тренинга указанной структуры, которое может получиться при разбиении пришедших n групп.
