2013年7月13日 星期六

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