# include <cstdio>
# include <cstdlib>
# include <cstring>
# include <algorithm>
using namespace std;
struct node
{
	char name[20];
	int num,a,b;
	bool operator<(const node &pos) const
	{
		if(num!=pos.num) return num<pos.num;
		else return strcmp(name,pos.name)<0;
	}
}res[105];
int dp[100005];
int main()
{
	int testcase;
	scanf("%d",&testcase);
	for(int test=1;test<=testcase;test++)
	{
		int n,m,num;
		scanf("%d%d%d",&n,&m,&num);
		for(int i=0;i<num;i++)
		{
			char str[50];
			scanf("%s",str);
			strcpy(res[i].name,strtok(str,":"));
			res[i].a=atoi(strtok(NULL,","));
			res[i].b=atoi(strtok(NULL," "));
			memset(dp,-1,sizeof(dp));
			dp[n]=0;
			for(int j=n;j>=m;j--)
			  if(dp[j]!=-1)
			  {
				  if(j/2>=m&&(dp[j/2]==-1||dp[j/2]>dp[j]+res[i].b))
					  dp[j/2]=dp[j]+res[i].b;
				  if(j-1>=m&&(dp[j-1]==-1||dp[j-1]>dp[j]+res[i].a))
					  dp[j-1]=dp[j]+res[i].a;
			  }
			res[i].num=dp[m];
		}
		sort(res,res+num);
		printf("Case %d\n",test);
		for(int i=0;i<num;i++)
			printf("%s %d\n",res[i].name,res[i].num);
	}
	return 0;
}