Maximizing Utilized Skills in Project Scheduling

You are given a set of employees and a list of projects. Each employee possesses a unique set of skills, and each project requires some skills along with a fixed number of hours to complete. You can select at most P projects out of the available list such that the total hours do not exceed 40. For any selected set of projects, the union of all required skills is considered utilized if and only if every required skill is possessed by at least one employee in the company.

Your task is to determine the maximum number of different skills that can be utilized by appropriately selecting projects under the given constraints.

The constraint on hours can be written in LaTeX as: \(\sum_{i=1}^{k} h_i \leq 40\), where \(h_i\) denotes the hours required for the \(i\)-th selected project and \(k\) is the number of selected projects (with \(1 \le k \le P\)).

inputFormat

The input is read from standard input (stdin) and has the following format:

T
E P N
(emp_1_skills)
(emp_2_skills)
... 
(emp_E_skills)
(proj_1_hours proj_1_skill1 proj_1_skill2 ...)
(proj_2_hours proj_2_skill1 proj_2_skill2 ...)
...
(proj_N_hours proj_N_skill1 proj_N_skill2 ...)
... (repeat the above for each test case)

</p>

Where:

• T is the number of test cases.
• For each test case, the first line contains three integers: E (number of employees), P (maximum number of projects you can choose) and N (the actual number of available projects).
• The next E lines each describe an employee's skills as space-separated integers.
• The following N lines each describe a project. The first integer is the number of hours required by the project, followed by the list of required skills (space-separated integers).

outputFormat

For each test case, output a single integer on a separate line (stdout) denoting the maximum number of different skills that can be utilized for that test case if the projects are optimally selected under the given constraints.

## sample

3
3 3 4
1 2 5
1 3
2 4 5 6
8 1 2
5 1 3
10 2 3
6 2 4 5
2 2 2
1 2
3 4
5 1 3
10 2 4
3 3 3
1 2 3
4 5 6
7 8 9
8 1 2
5 4 5
10 7 8

5
4
6

</p>