Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito es un burócrata que tiene un serio problema, se le está acumulando cientos de papeles de expedientes en su escritorio sin procesar. Y su jefe le está exigiendo que aumente su productividad para que al final del día todos los papeles estén procesados.  Actualmente tiene N expedientes en su escritorio sin procesar y su jefe demanda que solo queden M expedientes sin procesar al final del día. Por lo que nuestra tarea es ayudarlo a procesar la mayor cantidad de expedientes.  Hay varios software de varias compañías que permiten el procesamiento de los expedientes, por A pesos reducen el trabajo en una unidad y por B pesos reducen el trabajo en la mitad (se redondea de ser necesario).  Note que el trabajo no puede reducirse menos que 0. Por lo que debemos darle a Fito una tabla ordenada por nombres de software y sus costos para resolver el problema.

Input

La primera línea de la entrada es un entero que representa la cantidad de casos de prueba. Luego por cada caso de prueba la primera línea es tres enteros positivos separados por un espacio, N : la cantidad de expedientes a procesar, M la cantidad de expedientes que se deben de quedar sin procesar al final del dia y L que es la cantidad de software que permiten hacer el trabajo(1<=M<=N<=100000,1<=L<=100). Las próximas L líneas tienen el formato “[Nombre Software]:A,B”, donde A y B son los precios descritos anteriormente(0<=A,B<=10000), El nombre del software es una cadena cuya longitud oscila entre 1 y 16 y solo tiene letras mayúsculas. Estos nombres no se repiten.

Output

Por cada caso de prueba se debe imprimir “Caso X”, donde X es el número de  caso de prueba y luego una tabla de los software y el costo mínimo que se les pagaría ordenados ascendentemente por el costo. Los que tengan igual costo se ordenan por el nombre de la empresa.

Sample test(s)

Hints

Note que en el caso 1, si se usa el soft de la empresa C lo menos que se pagaría fuera 7,  si se paga 1 quedan 50 expedientes, luego por 1 más quedan 25, luego por 1más  quedan 12, luego por más 1 quedan 6 y finalmente por 3 quedan 5.