Another Easy Problem

Time Limit: 5000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)


Nowadays, many universities no longer force students to follow a fixed curriculum; instead they allow students to choose the courses on an individual basis. However, new programs need to be written to satisfy such needs. Your job is to write such a program.
In our system, the following objects exist: Time Period, Course and Student. The relationships between the three objects are as follows:
A course has a capacity, and is associated with multiple time periods; a student can register for multiple courses in the system (resulting in a possibly conflicting schedule).
To resolve possible conflicts with the schedules as well as to ensure that the number of students registered for each course does not exceed its capacity, the system will use the logic described below to determine the result:
Process courses, in the order they appear in the input.
For each course: Check each student's request in the order it is received, and reject the request if a) accepting the request will result in a conflict in the student's schedule, or b) if no more students could be accepted by this class, or c) the student has already enrolled in this class; otherwise, the request is accepted.

Can you solve this easy problem?


There are multiple test cases in the input file.
Each test case starts with three integers, N, M and R (1 <= N <= 20, 1 <= M <= 20, 0 <= R <= N * M), the number of students, the number of courses, and the number of requests, respectively.
Each of the following N lines contains one string, the ID of the student. The ID will contain no characters other than '0'...'9' The next part of each test case consists of M lines, each of which contains three integers, I, C, T, (C <= 100, T <= 30), the ID of the course, the capacity, and the number of time periods used by the course respectively; T more integers follows, representing the unique identifiers of the time periods. The description for the requests comes next, each line in the format of [Student ID](Space character)[Course ID], in the order as the requests are received. It is guaranteed that the requests are always valid, i.e., both the student ID and the course ID could be found in the description given above.
Two consecutive test cases are separated by a blank line. Input ends with End-of-File.


For each test case, print the total number of requests accepted by the system, in the format as indicated in the sample output.

Sample Input

2 2 4 0 1 101 1 2 3 4 102 2 1 5 0 101 1 102 1 101 0 102 1 1 0 4 5 1 1 5

Sample Output

Case 1: 3 Case 2: 0




2008 Asia Hangzhou Regional Contest Online