10670 - Work Reduction

Problem C: Work Reduction

文書已經堆滿了辦公桌，且在工作場所感到十分緊張， 老闆開始威脅你，如果今天內沒有任何進展，你將會被解雇！現在有 N 份文書處理，老闆確切地要求你只留下 M 份文書。

現在唯一的希望就是委外，有很多種許多種可以減少文書工作的公司，而每個公司提供兩種減少方案：

• 付 $A，他們將會減少一單位的文書
• 付 $B ，他們將會減少一半的文書(無條件捨去)

文書量不會少於 0。你將要選擇一間公司進行委外，但先根據花費由小到大列出清單(相同時按照字典順序)，再來挑選。


輸入第一行會有一個整數表示測資組數。

每組測資會有三個整數 N, M, L, (1 <= M <= N <= 100000, 1 <= L <= 100) 分別表示當前文書量、離開前的文書量以及可以委外的公司量。
接下來有 L 行，格式如 "[公司名稱]:A,B"，A、B 為上述描述的費用 (0 <= A,B <= 10000)，公司名字最多為 16 個大寫字母且不會重覆。

對於每組測資，輸出  "Case X" 測資組編號，接著按照花費由小到大輸出花費以及公司名稱，相同時按照公司名稱的字典順序。詳細參考範例輸出。

Sample Input

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

Sample Output

Case 1
C 7
B 22
A 37
Case 2
E 0
A 1
D 1
C 10
B 50

---

Gilbert Lee