$描述$
你的办公桌上文书工作开始堆积如山，工作场所的紧张气氛也日益加剧。老板威胁说，如果你在当天结束前没有任何进展，就会解雇你。目前你桌上有$N$单位的文书工作，而老板要求你在下班时必须恰好剩下$M$单位的文书工作。

现在你唯一的希望是雇佣帮手。有多家机构提供文书减负计划：

• 支付$A$美元，他们会将你的文书工作减少$1$单位。
• 支付$B$美元，他们会将你的文书工作总量减少一半（必要时向下取整）。

注意，文书工作的数量永远不能减少到小于$0$。

你的任务是生成一个排序表格，列出各机构的名称及其解决你工作量问题的最小成本。

$输入$
输入的第一行是一个正整数，表示接下来测试用例的数量。每个测试用例以三个用空格分隔的正整数开头：$N$（初始工作量）、$M$（目标工作量）和$L$（可用的减负机构数量），其中$1 \leq M \leq N \leq 100000$，$1 \leq L \leq 100$。接下来的$L$行格式为“[机构名称]:A,B”，其中$A$和$B$是该机构提供的上述收费标准（$0 \leq A,B \leq 10000$）。机构名称的长度在$1$到$16$之间，仅包含大写字母，且所有机构名称唯一。

$输出$
对于每个测试用例，先输出一行“Case X”，其中$X$为测试用例的编号。随后输出机构名称及其对应最小成本的表格，按最小成本非递减顺序排序；若最小成本相同，则按机构名称的字母顺序排序。表格中每行的格式为：机构名称，后跟一个空格，再跟该机构解决问题所需的最小成本。

输入数据 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

输出数据 1

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