Roller Coaster Scheduling (Small)

Time limit5sMemory limit512 MB

Summary

Given tickets for specific seats and customers, find the minimum rides needed after freely moving tickets to smaller-numbered seats, and the minimum promotions achieving it.

Level: Medium7 of 10
Topics: Greedy, Sorting, Simulation, Implementation
Solved: No attempts yet

Problem

A new roller coaster is about to open. Its train is a single row of $N$ seats, numbered 1 through $N$ from front to back. Seats closer to the front are worth more. Customers already bought tickets for opening day. One ticket lets one specific customer take one ride in one specific seat, and a customer who bought several tickets expects one ride per ticket.

You decide how many rides run on opening day. On a single ride each seat holds at most one customer, and seats may stay empty. A customer cannot sit in two seats on the same ride, and two customers cannot sit in the same seat on the same ride.

Fewer rides cost less, so you want the smallest possible number of rides. To lower that number you may promote any number of tickets. Promoting a ticket means handing the customer a ticket for a seat closer to the front, that is, a seat with a smaller number. You also want as few promotions as possible, because customers who get promoted ask for more promotions later. Moving one ticket from seat 4 to seat 2 counts as one promotion, not two.

Given every ticket that was sold, report the smallest number of rides that honors all tickets when you promote as much as needed and schedule the rides optimally, together with the smallest number of promotions that reaches that number of rides.

Input

The first line has the number of test cases $T$ . Each test case starts with one line holding three integers: $N$ , the number of seats in the train, $C$ , the number of potential customers, and $M$ , the number of tickets sold. Customers are numbered 1 through $C$ . Then $M$ lines follow, the $i$ -th of them holding two integers $P_i$ , the seat assigned to the $i$ -th ticket, and $B_i$ , the customer who bought that ticket.

$1 \le T \le 100$
$2 \le N \le 1000$
$1 \le C \le 1000$
$1 \le M \le 1000$
$1 \le P_i \le N$
$1 \le B_i \le C$

Output

For each test case, print one line in the form Case #x: y z, where x is the test case number starting from 1, y is the smallest number of rides that honors all tickets with optimal promotions and scheduling, and z is the smallest number of promotions needed to honor all tickets in y rides.

Note

In the first sample case both customers hold a ticket for seat 2. A single ride cannot honor both tickets, but promoting either ticket to seat 1 puts both customers on the same ride.

The second sample case is similar, except that both tickets are for seat 1. No seat sits in front of seat 1 and a ticket is never downgraded, so the two customers ride separately.

In the third sample case one customer holds both tickets. That customer rides twice no matter how the seats are arranged, so no promotion helps.

The fourth sample case shows that some seats and some customers may hold no ticket at all. Three tickets are sold for seat 3. Promote customer 2 to seat 2, and one ride can carry customer 1 in seat 2 and customer 3 in seat 3, while a second ride carries customer 2 in seat 2 and customer 1 in seat 3. More promotions cannot lower the ride count, because customer 1 holds two tickets and those two tickets go on different rides whatever the seats are.

In the fifth sample case, one optimal choice is to promote one of the two 3 1 tickets to seat 1.

Examples1

Example 1

Input

5
2 2 2
2 1
2 2
2 2 2
1 1
1 2
2 2 2
1 1
2 1
1000 1000 4
3 2
2 1
3 3
3 1
3 3 5
3 1
2 2
3 3
2 2
3 1

Expected output

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