Let's Go to the Movies
Улюблене заняття для великих родин в Акместані — це похід у кіно. Часто можна побачити, як кілька таких багатопоколінних родин разом йдуть дивитися фільм. Кінотеатри в Акместані пропонують два типи квитків: одиночний квиток, призначений для однієї особи, та сімейний квиток, який дозволяє батькам та їхнім дітям увійти до кінотеатру. Зрозуміло, що сімейний квиток завжди дорожчий за одиночний, іноді до п'яти разів.
Родинам досить складно вирішити, яка комбінація квитків є найбільш економічною для покупки. Наприклад, родина, зображена на малюнку праворуч, має чотири варіанти вибору квитків: сім одиночних квитків; два сімейні квитки; один сімейний квиток (для Адама, Боба, Сінді) плюс чотири одиночні квитки для решти; або один сімейний квиток (для Боба та його чотирьох дітей) плюс одиночні квитки для двох, що залишилися.
Напишіть програму, яка визначить, яка комбінація квитків має найменшу ціну. Якщо є більше ніж одна така комбінація, виведіть ту, яка має найменшу кількість квитків.
Вхідні дані
Ваша програма буде перевірена на одному або більше тестових випадках. Перша строка кожного тестового випадку містить два додатні цілі числа (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 — загальна вартість квитків.