Имя: Пароль: Зарегистрироваться Восстановить пароль
20/09/2024 11:33:33

# Рабочее место участника

## Задачи

953. Movies

Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)

A favorite pastime for big families in Acmestan is going to the movies. It is quite common to see a number of these multi-generation families going together to watch a movie. Movie theaters in Acmestan have two types of tickets: a single ticket is for exactly one person while a family ticket allows a parent and their children to enter the theater. Needless to say, a family ticket is always priced higher than a single ticket, sometimes as high as five times the price of a single ticket. It is quite challenging for families to decide which ticket arrangement is most economical to buy. For example, the family depicted in the figure on has four ticket arrangements to choose from:
• Seven single tickets;
• Two family tickets;
• One family ticket (for 0, 1, 2) plus four single tickets for the rest;
• Or, one family ticket (for 1 and his four children) plus single tickets for the remaining two.
Write a program to determine which ticket arrangement has the least price.
Input
The first line of the input includes two positive integers (S and F) where S is the price of a single ticket and F is the price of a family ticket. The remaining lines of the test case are either the name of a person going by him/herself, or of the form:
N_1\ N_2\ N_3\ …\ N_k
where N_1 is the ID of a parent, with N_2\ …\ \ N_k being his/her children. ID's are non-negative integers less then 100,000. No parent will be taking more than 1000 of their children to the movies . ID's unique, the ID of a particular person will appear at most twice: once as a parent, and once as a child. There will be at least one person and at most 100,000 people.
Output
Write the minimal total cost of tickets.

Sample Input 1

1 3
0 1 2
1 3 4 5 6


Sample Output 1

5


Sample Input 2

1 2
0
1
2
3


Sample Output 2

4

Source: ICPC Arab and North Africa RC, 2007