Problemsetting#1396
It's well-known that different programming contests require different types of problems. For example, the maximal array size for a TopCoder problem is only , and you definitely cannot give a Suffix Tree problem to IOI, because children will not have a chance to solve it (except for some that are particularly enthusiastic). Thus, not every problem is suitable for every contest.
You are preparing problemsets for different contests. These contests require different numbers of problems depending on the type. For example, an ACM ICPC style problemset usually has problems, TopCoder SRM – , and so on.
Luckily, you have already prepared different problems. For each problem, you have determined the set of contests that you can use that problem for. Also, you know the required number of problems for each contest.
Find the maximal number of different contests for which you can simultaneously compose complete problemsets from the given set of problems. All the problems in the problemsets must be unique, that is, no problem may be used twice in different problemsets.
The input file contains several test cases.
The first line of each test case contains integers and (1 \leq N \leq 15, 0 \leq M \leq 50) – the number of different contests and the number of prepared problems. Each of the following lines contains the name of a contest followed by the required number of problems for that contest. The name of a contest consists of lower- and uppercase Latin letters and/or digits, is not empty and does not exceed characters. Contest names are case-sensitive. It is guaranteed that all contest names will be pairwise different. The required number of problems does not exceed .
Each of the following lines contains a (possibly empty) list of acceptable contest names for each problem, separated by a single space. It is guaranteed that all contest names will be correct (i.e., those appearing in the previous section of the current test case) and unique.
The line containing two zeroes indicates the end of the input file.
For each test case, print the answer for that case on a new line, as shown in the sample output.
Пример 1