Problem E
Shopping Plan

You have a list of items you need to buy today, and you know the locations (represented as points on a cartesian grid) of a few stores in the area. You also know which of these stores are selling each item on your list, and at what price each store sells it. Given the price of gas, what is the minimum amount you need to spend in order to buy all the items on your shopping list and then drive back home? You start and end the journey at your house, which is located at (0,0).

To make matters interesting, some of the items on your list may be perishable. Whenever you make a purchase that includes one or more perishable items, you cannot drive to another store without first stopping back at your house. Every item on your shopping list is guaranteed to be sold by at least one store, so the trip will always be possible.

Input

The first line of input gives the number of cases, $T\leq 100$. $T$ test cases follow. Each case is a line formatted as

num_items num_stores price_of_gas

The next line contains the $num\_ items$ items on your shopping list. The items will be space separated, and each item will consist of only lowercase letters. If an item is perishable, its name will be followed by a single exclamation point. There will be no duplicate items on your list. The next $num\_ stores$ lines will each be formatted as

x_pos y_pos item1:price1 item2:price2 ...

Each of these lines gives the location of one store, along with the items available at that store and their corresponding prices. Only items which are on your shopping list will appear in these lists. Perishable items will not end with exclamation points on these lists. No item will be repeated in a store’s list. Each store will offer at least one item for sale. No two stores will be at the same location, and no store will be located at (0,0).

You may assume that $0 \leq price\_ of\_ gas \leq 1000$ and $-1000 \leq x\_ pos, y\_ pos \leq 1000$. All prices will be positive integers at most 1000. Finally, $1 \leq num\_ items \leq 5$ and $1 \leq num\_ stores \leq 10$.

Output

For each test case, output one line containing "Case #$x$: " followed by the minimum possible cost of the trip. Your output will be accepted if its relative or absolute error is less than $10^{-7}$. Don’t forget about $price\_ of\_ gas$, which is the amount of money you must spend per unit distance that you drive.

2
1 2 10
cookies
0 2 cookies:400
4 0 cookies:320
3 3 5
cookies milk! cereal
0 2 cookies:360 cereal:110
4 0 cereal:90 milk:150
-3 -3 milk:200 cookies:200

Case #1: 400.000000000
Case #2: 519.292068965