Let's Go to the Movies

Time limit1sMemory limit128 MB

Summary

Each family is a parent with children, and tickets are either singles or family tickets (one parent plus any subset of their own children). Find the arrangement minimizing cost, breaking ties by fewest tickets.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Tree
Solved: No attempts yet

Problem

A favorite pastime for big families in Acmestan is going to the movies. It is quite common to see several multi-generation families going together to watch a movie. Movie theaters in Acmestan sell two kinds of tickets: a single ticket admits exactly one person, while a family ticket admits a parent together with their children. A family ticket is always more expensive than a single ticket — sometimes as much as five times the price.

Deciding which combination of tickets is cheapest can be tricky. For example, the family shown in the figure can choose among four arrangements: seven single tickets; two family tickets; one family ticket (for adam, bob and cindy) plus four single tickets for the rest; or one family ticket (for bob and his four children) plus single tickets for the remaining two.

Write a program that determines the cheapest arrangement of tickets. If several arrangements cost the same, choose the one that uses the fewest tickets.

Input

The input consists of one or more test cases. The first line of each test case contains two positive integers $S$ and $F$ : the price of a single ticket and the price of a family ticket, respectively. Each of the following lines is either the name of a person who is going alone, or has the form

N1 N2 N3 ... Nk

where $N_1$ is a parent and $N_2, \ldots, N_k$ are that parent's children. All names consist of lower-case letters and are at most 1000 characters long. No parent brings more than 1000 children to the movies. Names are unique; any given name appears at most twice — once as a parent and once as a child. Each test case describes at least 1 and at most 100000 people.

A test case ends where the next one begins (a line containing two integers). The very last test case is followed by a line containing two zeros.

Output

For each test case, print a line in the format

k. NS NF T

where $k$ is the test-case number (starting from 1), $NS$ is the number of single tickets, $NF$ is the number of family tickets, and $T$ is the total cost. The values are separated by single spaces.

Examples4

Example 1

Input

1 3
adam bob cindy
bob dima edie fairuz gary
1 2
john
paul
george
ringo
1 3
a b c
0 0

Expected output

1. 2 1 5
2. 4 0 4
3. 0 1 3

Example 2
Input
```
5 10
alice
0 0
```
Expected output
```
1. 1 0 5
```
Example 3
Input
```
2 5
mom ann bea cob
0 0
```
Expected output
```
1. 0 1 5
```
Example 4
Input
```
2 3
gran par
par kid
0 0
```
Expected output
```
1. 1 1 5
```