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.

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want. Be careful with extra whitespace. The output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you have to solve the test phase before you can submit your code. You must provide the source code used to solve the challenge and you can only make one submission. After your solution is submitted, you won't be able to modify it to fix issues or make it faster.

If you have any doubts, please see the info section.