Tuenti Challenge 10

Challenge 16 - The new office

You work for one of the leading technology companies in the sector, and it is in expansion. With the latest batch of new hires, the building has to be adapted to get more usable space. The problem is that while the works are in progress, some floors don't have restrooms. To mitigate the bottleneck in the rush hour, the company decided to build more restrooms.

Each employee has access to different floors depending on their role. As a software engineer, you are tasked with finding the minimum number WC's that would allow all of the employees to use the WC simultaneously. The only restriction is that there has to be the same number of WC's on every floor.

Input

The first line has an integer C, which is the number of cases for the problem.
Each case starts with a line with two integers, F and G, indicating the number of floors and employee groups. Then, two additional lines per employee group follow:

  • The first line has two numbers: Ei, the number of employees belonging to the group; and Ni, the number of floors this group has access to.
  • The second line contains the specific floor numbers the group members are allowed to access (as many as specified in the previous line). Floors are indexed from 0 to F-1.

Output

For each case, output a line starting with "Case #x: " followed by the minimum number of WC's that would allow all the employees to use the WC simultaneously.

Limits

1 ≤ C ≤ 10
1 ≤ F ≤ 2000 for up to 1 case, 500 for the rest
1 ≤ G ≤ 400 for up to 1 case, 100 for the rest
1 ≤ Ei, NiF

Sample Input

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

Sample Output

Case #1: 1
Case #2: 5
Case #3: 2

In the first case, there are two employees and two floors. One employee can access one of the floors and the other can access both floors, so one WC per floor is enough.
In the second case, there are five employees in one floor. We clearly need five WCs.
In the third case, we need 2 WCs per floor.

Problem stats

Completion time: min: 0:15:56 h
10th percentile: 0:58:43 h
90th percentile: 22:27:22 h
max: 54:49:47 h
Test phase time: 10th percentile: 0:56:54 h
90th percentile: 18:13:50 h
Submit phase time: 10th percentile: 0:01:28 h
90th percentile: 2:16:12 h
# of completions:51