Programming Contests

Every programming contest features a different kind of problem. For example, TopCoder caps the maximum array size at 50. Also, IOI is a contest that children take part in, so Suffix Tree problems do not appear.

Woohyun writes problems for $N$ distinct programming contests. Each contest needs a different number of problems. For instance, an ACM-ICPC-style contest usually needs 10 problems, while a TopCoder SRM needs 5.

Woohyun has prepared $M$ problems in advance and, for each problem, has decided which contests it may be used in.

Assuming every contest is to be held at the same time, determine the maximum number of contests that can actually run. To hold a contest, all of its required problems must be filled, and each problem may be used in at most one contest.

The input consists of several test cases.

The first line of each test case contains the number of contests $N$ and the number of prepared problems $M$ ($1 \le N \le 15$, $0 \le M \le 50$).

Each of the next $N$ lines contains a contest name and the number of problems that contest needs to run. A contest name consists of upper- and lower-case letters and digits, is at most 100 characters long, and is case-sensitive. The required problem count is at most 100.

Each of the next $M$ lines lists, separated by spaces, the names of the contests in which that problem may be used. If a problem cannot be used in any contest, its line is empty.

The last line of the input contains two 0s and is not processed.

For each test case, print on one line the maximum number of contests that can be held simultaneously, together with the case number. If the answer for the $k$-th test case is $c$, print it in the format Case #k: c.