Roller Coaster Scheduling (Large)

You built a new roller coaster and it opens soon. The train is a single row of $N$ seats, numbered 1 through $N$ from front to back. Seats closer to the front are worth more. Tickets for opening day are already sold. One ticket lets one specific customer take one ride in one specific seat. Some customers bought more than one ticket, and each of them expects one ride per ticket.

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

To cut operating costs you want the smallest number of rides that honors every ticket. To lower that number you may promote any number of tickets. Promoting a ticket means taking a customer's ticket back and handing that customer a new 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 frequent promotions make customers ask for more of them later.

The seat and the buyer of every ticket sold are given. Find the smallest number of rides that honors all tickets when you use promotions freely and schedule the rides optimally, and the smallest number of promotions needed to keep that number of rides. Moving one customer's ticket from seat 4 to seat 2 counts as one promotion, not two.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains three integers $N$, $C$, and $M$: the number of seats on the coaster, the number of customers, and the number of tickets sold. Customers are numbered from 1 to $C$. Each of the next $M$ lines contains two integers $P_i$ and $B_i$: the seat assigned to the $i$-th ticket and the number of the customer who bought that ticket.

Limits

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

For each test case, print one line in the form Case #x: y z. Here $x$ is the test case number starting from 1, $y$ is the smallest number of rides that honors all tickets under an optimal choice of promotions and schedule, and $z$ is the smallest number of promotions that lets you honor all tickets in $y$ rides.

In test case 1 of the sample, both customers bought a ticket for seat 2. A single ride cannot honor both tickets, but promoting either ticket to seat 1 seats both customers on one ride.

Test case 2 is similar, except that both tickets are for seat 1. Nothing is closer to the front than seat 1 and you cannot hand out a worse seat, so each customer needs a ride of their own, two rides in total.

In test case 3 the same customer bought both seats. That customer alone forces two rides, so there is no reason to give any promotion.

Test case 4 shows that a customer or a seat may hold no ticket at all. Three tickets were sold for seat 3 there. Promote customer 2 to seat 2, for example. The first ride then seats customer 1 in seat 2 and customer 3 in seat 3, and the second ride seats customer 2 in seat 2 and customer 1 in seat 3. Further promotions do not reduce the number of rides, because customer 1 holds two tickets and those two go on different rides whatever the seats are.

In test case 5, one optimal answer promotes one of the 3 1 tickets to 1 1.