Давайте пойдем в кино
Любимое времяпрепровождение больших семей в Акместане — походы в кино. Часто можно увидеть, как несколько таких многопоколенных семей вместе идут смотреть фильм. Кинотеатры в Акместане предлагают два типа билетов: одиночный билет, предназначенный для одного человека, и семейный билет, который позволяет родителю и его детям войти в кинотеатр. Семейный билет всегда стоит дороже одиночного, иногда в пять раз дороже.
Семьям бывает сложно выбрать наиболее экономичную комбинацию билетов. Например, у семьи, изображенной на рисунке справа, есть четыре варианта выбора билетов: семь одиночных билетов; два семейных билета; один семейный билет (для Адама, Боба, Сэнди) плюс четыре одиночных билета для остальных; или один семейный билет (для Боба и его четырех детей) плюс одиночные билеты для оставшихся двух.
Напишите программу, которая определяет, какая комбинация билетов будет стоить наименьше. Если таких комбинаций несколько, выберите ту, которая использует наименьшее количество билетов.
Входные данные
Ваша программа будет протестирована на одном или нескольких тестовых случаях. Первая строка каждого тестового случая содержит два положительных целых числа (S и F), где S — цена одиночного билета, а F — цена семейного билета. Оставшиеся строки тестового случая содержат либо имя человека, идущего самостоятельно, либо имеют вид:
N_1 N_2 N_3 … N_k
где N_1 — имя родителя, а N_2 … N_k — его/ее дети. Имена состоят из строчных букв и не длиннее 1000 символов. Ни один родитель не возьмет с собой в кино более 1000 детей :-). Имена уникальны, имя конкретного человека может появиться максимум дважды: один раз как родитель и один раз как ребенок. В любом тестовом случае будет как минимум один человек и не более 100000 человек.
Конец тестового случая определяется началом следующего тестового случая (строка, состоящая из двух целых чисел). Конец последнего тестового случая определяется двумя нулями.
Выходные данные
Для каждого тестового случая выведите результат в следующем формате:
k. NS NF T
Где k — номер тестового случая (начиная с 1), NS — количество одиночных билетов, NF — количество семейных билетов, а T — общая стоимость билетов.