Tuenti Challenge 8

Challenge 11 - Lasers

One of the most prestigious jewelry shops in the world is having a unique week long exposition of their best items.

The venue will be one of the most secure in the world. An NxM meter rectangular room with perpendicular lasers and sensors on opposing walls, separated by one meter, with a maximum of N + M lasers.

The hosts are happy with the security provided, but they're also worried about the items, which are extremely delicate and continuous exposure to lasers could damage them. Specifically, items can only be hit by one laser.

To simplify things, a laser is considered to hit an item when it goes through the 1 x 1 meter cell containing the item.

The hosts have come to you with the arrangement of the items. As chief of security for the venue it's your job to maximize the security of the event or, in other words, to cram as many lasers as possible in the venue without upsetting the hosts.

Input

The first line contains an integer C, which is the number of cases for the problem.
Each case starts with a line with three integers N, M and I, which are the dimensions of the venue and the number of items. I lines follow, each with two integers A and B, that indicate that an item is in position (A, B).

Output

For each case, there should be a line starting with "Case #x: " followed by the maximum number of lasers that fit in the venue.

Examples

Case 1:

3 3 0









Case 2:

3 3 9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
Case 3:

3 4 4
0 1
1 2
2 0
2 3





Case 4:

4 4 6
0 0
0 1
1 2
1 3
2 1
3 0



In Case 1 the answer is 6. You can completely fill the venue with lasers:

Case 1

In Case 2 the answer is 3. You can only put lasers in one of the two walls:

Case 2

In Case 3 the answer is 4. This is a possible arrangement:

Case 3

In Case 3 the answer is 5. This is a possible arrangement:

Case 4

Limits

  • 1 ≤ N, M ≤ 500
  • 0 ≤ IN*M

Sample Input

4
3 3 0
3 3 9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
3 4 4
0 1
1 2
2 0
2 3
4 4 6
0 0
0 1
1 2
1 3
2 1
3 0

Sample Output

Case #1: 6
Case #2: 3
Case #3: 4
Case #4: 5

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 to. Be careful with extra whitespaces, 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 first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

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

Problem stats

Completion time: min: 0:09:39 h
10th percentile: 0:22:27 h
90th percentile: 32:05:46 h
max: 128:43:37 h
Test phase time: 10th percentile: 0:19:44 h
90th percentile: 17:26:51 h
Submit phase time: 10th percentile: 0:00:44 h
90th percentile: 21:54:10 h
# of completions:50