It's somewhat natural, at the start of each semester, that we go to some classroom to have a lesson unwillingly, only to find it filled up with students from another class. I wonder how they are arranging the resources. So that's why I'm currently engaged in a classroom scheduling project.
Time being extremely tight, I have to focus on the overall system behaviors, leaving the core, but difficult part unfinished. That's the classroom auto-arrangement engine. But I'm not worried, because I can ask for help here.
Let's consider an easier scenario first.
We have many classroom buildings, each belonging to a specific academy. Every classroom inside is associated with its capacity. Now, at the start of a semester, we got a lot of course requests by each academy to be scheduled simultaneously in these classrooms. Certainly, a course can only be scheduled to a classroom where the number of attending students is no greater than the classroom's capacity. Note that these courses should be held simultaneously without resource conflicts, situations such as holding course A on Monday and course B on Tuesday should not be considered.
The best scheduling plan is defined as follows:
The plan must meet a maximum count of course requests.
The count of courses not arranged in the building their academy possesses should be minimized, provided that condition 1 is met. This eases the management and saves a lot of campus-wide commuting.
Input
There are multiple test cases.
The first line of ease test case contains the number A of academies in the university. A line with A = 0 ends the input data, and this should not be processed.
Next, there are A lines describing each academy, with an integer C, the count of classrooms in the building the academy possesses, followed by C integers not more than 200, stating the capacity of each classroom. The identifier for each academy starts at one.
Note that the overall number of classrooms in the university is at most 100.
This is followed by R (0 < R <= 100), the count of course requests, and hence R lines describing each request in the format Ai Si, where Ai stands for the academy submitting the course request and Si being the total number of students attending the course.
Output
For each test case, you should produce one line of output, consisting of two numbers separated by exactly one space: the maximum count of course requests met, and the minimum count of course not arranged in the building their academy possesses, out of the total arranged courses.
Sample Input
2
3 100 100 100
3 50 50 50
7
1 50
1 50
1 100
2 50
2 50
2 100
2 200
0
Sample Output
6 2
