Headmaster’s Headache

The headmaster of Spring Field School is considering employing some new teachers for certain sub- jects. There are a number of teach- ers applying for the posts. Each teacher is able to teach one or more subjects. The headmaster wants to select applicants so that each sub- ject is taught by at least two teach- ers, and the overall cost is mini- mized. Input The input consists of several test cases. The format of each of them is explained below: The first line contains three positive integers S, M and N. S (≤ 8) is the number of subjects, M (≤ 20) is the number of serving teachers, and N (≤ 100) is the number of applicants. Each of the following M lines describes a serving teacher. It first gives the cost of employing him/her (10000 ≤ C ≤ 50000), followed by a list of subjects that he/she can teach. The subjects are numbered from 1 to S. You must keep on employing all of them. After that there are N lines, giving the details of the applicants in the same format. Input is terminated by a null case where S = 0. This case should not be processed. Output For each test case, give the minimum cost to employ the teachers under the constraints. Sample Input 222 10000 1 20000 2 30000 1 2 40000 1 2 000 Sample Output 60000