Work Reduction

Paperwork is piling up on your desk, and tension at work is rising. Your boss has threatened to fire you unless you make progress by the end of the day. Right now you have $N$ units of paperwork on your desk, and your boss demands that exactly $M$ units remain by the end of the day.

Your only hope is to hire help. Several agencies offer paperwork-reduction plans, and each agency offers the following two operations:

• For $A they reduce your paperwork by one unit.
• For $B they reduce your entire paperwork by half (rounding down when the amount is odd).

Paperwork can never be reduced below 0.

Your task is to print, for each agency, its name together with the minimum cost of using that agency to reach your target, as a sorted table.

The first line of input contains a single positive integer, the number of test cases that follow. Each test case begins with three space-separated positive integers $N$, $M$, and $L$: $N$ is your starting workload, $M$ is your target workload, and $L$ is the number of available agencies ($1 \le M \le N \le 100000$, $1 \le L \le 100$). The next $L$ lines each have the form NAME:A,B, where $A$ and $B$ are that agency's rates as described above ($0 \le A, B \le 10000$). Each agency name has length between 1 and 16 and consists only of capital letters, and all agency names are unique.

For each test case, first print Case X on its own line, where $X$ is the case number. Then print the table of agency names and their minimum costs, sorted in non-decreasing order of minimum cost. Break ties among agencies with equal minimum cost alphabetically by agency name. On each line of the table, print the agency name, a single space, and the minimum cost for that agency to reach the target.