Work Reduction

Paperwork is beginning to pile up on your desk, and tensions
at the workplace are starting to mount. Your boss has
threatened to fire you if you don’t make any progress by the
end of the day. You currently have $N$ units of paperwork on your desk,
and your boss demands that you have *exactly*
$M$ units of paperwork
left by the end of the day.

The only hope for you now is to hire help. There are various agencies which offer paperwork reduction plans:

For $\$ A$ they will reduce your paperwork by one unit. For $\$ B$ they will reduce your entire paperwork by half (the amount of work left is rounded down to an integer when necessary).

Note that work can never be reduced to less than $0$.

Your task now is to produce a sorted table of agency names and their respective minimum costs to solve your workload problem.

The first line of input consists of a single positive
integer representing the number of cases to follow, at most
$250$. Each case begins
with three positive integers separated by spaces: $N$ – your starting workload,
$M$ – your target
workload, and $L$ – the
number of work reduction agencies available to you,
($1 \le M \le N \le 100\,
000$, $1 \le L \le
100$). The next $L$
lines have the format “[*agency name*]:$A$,$B$”, where $A$ and $B$ are the integer rates as described
above for the given agency ($0
\le A,B \le 10000$). The length of the agency name will
be between $1$ and
$16$, and will consist
only of capital letters `A`-`Z`. Agency names will be unique.

For each test case, print “`Case
$X$`”, with
$X$ being the case number,
on a single line, followed by the table of agency names and
their respective minimum costs, sorted in non-decreasing order
of minimum costs. Sort job agencies with identical minimum
costs in alphabetical order by agency name. For each line of
the table, print out the agency name, followed by a space,
followed by the minimum required cost for that agency to solve
your problem.

Sample Input 1 | Sample Output 1 |
---|---|

2 100 5 3 A:1,10 B:2,5 C:3,1 1123 1122 5 B:50,300 A:1,1000 C:10,10 D:1,50 E:0,0 |
Case 1 C 7 B 22 A 37 Case 2 E 0 A 1 D 1 C 10 B 50 |