/*Vamsi Kundeti (vamsi(dot)krishnak(at)gmail*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<math.h>
#include "List.h"
unsigned int **GRAPH;
//#define VERBOSE_MODE 1
unsigned int item_bits;
char **item_names;
unsigned int item_subset;
/*has a unsigned int indicating
*if this shop sells the item or not
*/
unsigned int *shop_sells;
/*dist[i][j] indicates the distance 
 *between i and j*/
double **dist;
/*cost[i][j] indicates the cost of
*item i in shop j
*/
double **cost;
/*The number of the items*/
unsigned int icount;
/*The number of test cases*/
unsigned int tcount;
unsigned int caseno;
/*The number of shops**/
unsigned int scount;
typedef struct _pair_ {
	int x;
	int y;
}Coor;
Coor *shop_coor;
void EnumSubSetsBFS(unsigned int n);
unsigned int LookUpItem(const char *key){
	unsigned int i=0;
	for(i=0;i<icount;i++){
		if(!strcmp(key,item_names[i])){
			return i+1;
		}
	}
	/*Ignore this item*/
	return 0;
}
unsigned int gas_price;
unsigned int perish;
inline char CheckPerish(unsigned int i){
	return (perish & (1<<(i)))?1:0;
}
void ReadInput(void){
	unsigned int i,j;
	unsigned int len;
	unsigned int icost;
	char item_buffer[64];
	char delim; 
	scanf("%u",&tcount);
	while(tcount--){
		perish=0;
		scanf("%u %u %u",&icount,&scount,&gas_price);
		assert(icount && scount);
		/*Read the items to be bought*/
		item_names = (char **) malloc(sizeof(char *)*icount);
		for(i=0;i<icount;i++){
			scanf("%s",&item_buffer);
			len = strlen(item_buffer);
			len = (len > 64)?64:len;
			item_names[i] = (char *) malloc(sizeof(char)*(len+1));
			assert(memcpy(item_names[i],item_buffer,(len+1))==item_names[i]);
			if(len && (item_names[i])[len-1]=='!'){
				perish = perish | (1 << (i));
				(item_names[i])[len-1]='\0';
			}
		}
		shop_coor = (Coor *) malloc(sizeof(Coor)*(scount+1));
		cost = (double **) malloc(sizeof(double *)*(scount+1));
		shop_sells = (unsigned int *)malloc(sizeof(unsigned int)*(scount+1));
		shop_coor[0].x = 0.0;
		shop_coor[0].y = 0.0;
		for(i=1;i<scount+1;i++){
			cost[i] = (double *) malloc(sizeof(double)*icount);
			scanf("%d %d",&(shop_coor[i].x),&(shop_coor[i].y));
			shop_sells[i] = 0;
			for(j=0;j<icount;j++){
				cost[i][j] = 0;
			}
			while(1){
				scanf(" %[^:]:%u",item_buffer,&icost);
				if(j=LookUpItem(item_buffer)){
					cost[i][j-1] = icost;
					/*Also set the sells bit_set*/
					shop_sells[i] = shop_sells[i] | (1<<(j-1));
				}
				scanf("%c",&delim);
				if(delim == '\n'){
					break;
				}
			}
		}
		/*Now Compute the distance matrix*/
		dist = (double **)malloc(sizeof(double *)*(scount+1));
		for(i=0;i<scount+1;i++){
			dist[i] = (double *)malloc(sizeof(double)*(scount+1));
			for(j=0;j<scount+1;j++){
				dist[i][j] = sqrtf((shop_coor[i].x - shop_coor[j].x)*
					(shop_coor[i].x - shop_coor[j].x) +(shop_coor[i].y - shop_coor[j].y)*
						(shop_coor[i].y - shop_coor[j].y));
			}
		}
#if 0
		printf("Items..\n");
		for(i=0;i<icount;i++){
			printf("%s ",item_names[i]);
		}
		printf("\n");
		printf("Cost Matrix\n");
		for(i=0;i<scount+1;i++){
			printf("(%d,%d)",shop_coor[i].x,shop_coor[i].y);
			for(j=0;j<icount;j++){
				if(cost[i][j]){
					printf(" %s[%c]:%lf",item_names[j],((CheckPerish(j))?'P':'U'),cost[i][j]);
				}
			}
			printf("\n");
		}
		printf("\n");
#endif
		/*Make the call to the dynamic programming routine*/
		EnumSubSetsBFS(icount);

		/*Freeup the stuff*/
		for(i=0;i<icount;i++){
			free(item_names[i]); 
		}
		free(item_names);
		free(shop_coor);
		free(shop_sells);
		for(i=1;i<scount+1;i++){
			free(cost[i]);
		}
		free(cost);
		for(i=0;i<scount+1;i++){
			free(dist[i]);
		}
		free(dist);
	}
}

void CreateGraph(unsigned int *n){
	unsigned int i,j;
	printf("Enter the Graph Size\n");
	scanf("%u",n);
	printf("Enter the weighted graph\n");
	GRAPH = (unsigned int **) malloc(sizeof(unsigned int *)*(*n));
	for(i=0;i<*n;i++){
		GRAPH[i] = (unsigned int *) malloc(sizeof(unsigned int)*(*n));
		for(j=0;j<*n;j++){
			scanf("%u",&(GRAPH[i][j]));
		}
	}
}


unsigned int subset_count=0;
int main(){
	/*Create the Graph*/
	unsigned int n;
	caseno=0;
	ReadInput();
	//EnumSubSetsBFS(n);

}
/*Returns the new tail of the list*/
inline List* ListAppend(List **tail,void *_data){
	List *new_node = (List *)malloc(sizeof(new_node)*1);
	assert(new_node);
	if(!(*tail)){
		(*tail) = new_node;
		(*tail)->_data = _data;
		(*tail)->next = NULL;
		return *tail;
	}
	new_node->_data = _data;
	new_node->next = NULL;
	(*tail)->next = new_node;
	return new_node;
}
typedef struct _subset_{
	/*if i^th bit is set then subset has i^th
	 *element*/
	unsigned int ebits;
	unsigned int max; /*Maximum element in the subset*/
	unsigned int size; /*Size of subset*/
	/*Pointer to the sub-problem S({},i,0) S({},i,1)*/
	void *sub_problem;
}SubSet;

/*Enumerate the Subset using BFS, n is 
 *the set size [1,2...n] */
void EnumSubSetsBFS(unsigned int n){
	unsigned int check_sub_set,k,i,j;
	unsigned int current_level = 0;
	List *bfs_list = NULL;
	List *tail = NULL; List *free_node,*ptr;
	SubSet *sub_set,*new_sub_set;
	SubSet *one_sets = NULL;

	one_sets = (SubSet *)malloc(sizeof(SubSet)*icount); 
	assert(one_sets);
	/*Add the 1-subsets i=items*/
	for(i=0;i<icount;i++){
		one_sets[i].ebits = 0; one_sets[i].ebits |= (1<<i);
		one_sets[i].max = i; one_sets[i].size = 1;
		/****SUBPROBLEM SPECIFIC*****/
		one_sets[i].sub_problem = (double **)malloc(sizeof(double *)*2);
		/* Perishable S({i},X,0) */
		((double **)one_sets[i].sub_problem)[0] = (double *) malloc(sizeof(double)*(scount+1));
		/* Unperishable S({i},X,1) */
		((double **)one_sets[i].sub_problem)[1] = (double *) malloc(sizeof(double)*(scount+1));
		double **sub_problem_i = (double **)one_sets[i].sub_problem;

		/*j is the shop*/
		for(j=1;j<scount+1;j++){
			/*if item i can be bought at shop j
			 *depending on perishable or not initialize sub_problem[0] 
			 *sub_problem[1]
			 */
			 sub_problem_i[0][j] = HUGE_VAL; sub_problem_i[1][j] = HUGE_VAL;
			 if(shop_sells[j]&(1<<i)){
				 if(CheckPerish(i)){
				 	sub_problem_i[0][j] = dist[0][j]*(gas_price) + cost[j][i];
				 }else{
				 	sub_problem_i[1][j] = dist[0][j]*(gas_price) + cost[j][i];
				 }
			 }
#ifdef VERBOSE_MODE
			printf("S({%u},%u,0) = %lf\n",i+1,j+1,sub_problem_i[0][j]);
			printf("S({%u},%u,1) = %lf\n",i+1,j+1,sub_problem_i[1][j]);
#endif
		}
		/*****************************/
		if(!tail){
			ListAppend(&bfs_list,(void *)&(one_sets[i]));
			tail = bfs_list;
			continue;
		}
		tail = ListAppend(&tail,(void *)&(one_sets[i]));
	}



	/*Now do the BFS*/
	while(bfs_list){
		sub_set = (SubSet *)bfs_list->_data; 
		free_node = bfs_list;
		bfs_list=bfs_list->next;
		subset_count++;
		assert(sub_set->max < icount);
		for(i=((sub_set->max)+1);i<icount;i++){
			new_sub_set = (SubSet *) malloc(sizeof(SubSet)*1);
			new_sub_set->size = (sub_set->size)+1;
			new_sub_set->max = i;
			new_sub_set->ebits = (sub_set->ebits | (1<<i));
			/*This subset enumeration is critical to Subset based D.P*/

			/*****<begin>**SUBPROBLEM SPECIFIC******/
			/* S(X,j) = min_k {S(X-k,k) + d[k][j]}*/
			ptr = free_node;
			double current_min = HUGE_VAL;
			double **new_sub_problem;
			double **sub_problem; double local_min;
			double local_min_perish,local_min_unperish;
			unsigned int k1,perish,shop1;
			List *ptr_prev;
			
			new_sub_set->sub_problem = (double **) malloc(sizeof(double *)*2);
			((double **)new_sub_set->sub_problem)[0] = (double *) malloc(sizeof(double)*(scount+1));
			((double **)new_sub_set->sub_problem)[1] = (double *) malloc(sizeof(double)*(scount+1));
			new_sub_problem = (double **)new_sub_set->sub_problem;

			for(perish=0;perish<=1;perish++){
				for(j=1;j<scount+1;j++){
					/*Objective here is to fill up S({new_sub_set},j,0) 
					 *and S({new_sub_set},j,1)*/
					ptr = free_node;
					current_min = HUGE_VAL;
					for(k=1;k<=new_sub_set->size;k++){
						do{
							check_sub_set = ((SubSet *)ptr->_data)->ebits; 
							check_sub_set ^= new_sub_set->ebits; 
							k1 = (int)log2(check_sub_set);
							ptr_prev = ptr;
							ptr=ptr->next;
						}while(check_sub_set & (check_sub_set-1));

						/*j is the shop and k1 is the item which you want
						 *to buy at this shop, depending on
						 *perishablity create the value of current min.
						*/
						if(!(shop_sells[j] & check_sub_set)){
							 continue; /*The shop don't sell this*/
						}
						sub_problem = (double **)
							((SubSet *)ptr_prev->_data)->sub_problem;
						/*item k1 is sold by shop j*/
						local_min = HUGE_VAL;
						if((perish && !CheckPerish(k1)) 
								|| (!perish && CheckPerish(k1))){
							for(shop1=1;shop1<scount+1;shop1++){
								/*S{{new_sub_set}-{k1},shop1} + 
								d(shop1,h) + d(h,j) + c[k1][j]*/
								if(j != shop1 || perish){
									local_min_perish = 
										sub_problem[0][shop1] + 
										(dist[shop1][0] + dist[0][j])*
											(gas_price) + cost[j][k1];
								}else if(!perish){
									local_min_perish = sub_problem[0][shop1] + 
										cost[j][k1];
								}
								local_min_unperish = sub_problem[1][shop1] + 
									(dist[shop1][j])*(gas_price) + cost[j][k1];
								local_min_perish = 
								 (local_min_perish < local_min_unperish)? 
									local_min_perish:local_min_unperish;

								if(local_min_perish < local_min){
									local_min = local_min_perish;
								}
							}
						}
						if(local_min < current_min){
							current_min = local_min; 
						}
					}
					new_sub_problem[perish][j] = current_min;
				}
			}

#ifdef VERBOSE_MODE
			printf("Printing S(V,i) size=%u \n",sub_set->size);
			/*Print SubSet*/
			unsigned int i1;
			for(i1=1;i1<scount+1;i1++){
				printf("S({");
				unsigned int j1;
				/*Get the elements back*/
				check_sub_set = new_sub_set->ebits;
				for(j1=0;j1<icount;j1++){
					if(check_sub_set & (1<<j1)){
						printf(" %u ",j1+1);
					}
				}
				printf("},%u,0)=%lf\n",i1+1,((double **)(new_sub_set->sub_problem))[0][i1]);
				printf("S({ABOVE},%u,1)=%lf\n",i1+1,((double **)(new_sub_set->sub_problem))[1][i1]);
			}
#endif

			/**********<END>****************/
			tail = ListAppend(&tail,(void *)new_sub_set);
		}

		if(sub_set->size == icount){
			double final_answer=HUGE_VAL;
			double local_min; double **sub_problem;
			sub_problem = (double **) sub_set->sub_problem;
			for(j=1;j<scount+1;j++){
				local_min = (sub_problem[0][j]<sub_problem[1][j])?
					sub_problem[0][j]:sub_problem[1][j];
				local_min += (dist[j][0])*(gas_price);
				if(local_min < final_answer){
					final_answer = local_min;
				}
			}
			printf("Case #%u: %0.7lf\n",++caseno,final_answer);
		}

		if(!(sub_set >= one_sets && sub_set <= &(one_sets[icount-1]))){
			free(((double **)sub_set->sub_problem)[0]);
			free(((double **)sub_set->sub_problem)[1]);
			free(sub_set->sub_problem);
			free(sub_set); 
		}
		free(free_node);
	}
	for(i=0;i<icount;i++){
		free(((double **)one_sets[i].sub_problem)[0]);
		free(((double **)one_sets[i].sub_problem)[1]);
		free(one_sets[i].sub_problem);
	}
	free(one_sets);
//	printf("SubsetCount=%u\n",subset_count);
}