Witch's Cauldron (part 3)

Note: this problem is similar to Witch's Cauldron (part 2), but adds toxic products.

A witch has a set of $N$ base ingredients, each available in infinite quantity. She also has $M$ recipes.

Each recipe specifies:

the name of the product it produces,
a list of required ingredients (each with a quantity), and
the number of minutes needed to brew the product.

An ingredient required by a recipe can be either a base ingredient or the result of another recipe. Multiple recipes may produce the same ingredient, in which case the witch may choose whichever method is faster.

Among the products that occur in recipes, $K$ distinct products are toxic. The witch must take special care when brewing them:

Brewing one unit of a toxic product immediately after another unit of the same toxic product is safe and requires no extra time.
However, if she brews a unit of a toxic product and then wants to brew anything else (a different toxic product or any non-toxic product), she must first clean the cauldron. Cleaning takes exactly $C$ minutes.
Brewing non-toxic products never requires cleaning.

The witch wants to produce exactly one unit of witch's brew. Determine the minimum total brewing time needed.

Input

The first line contains an integer $T$ — the number of test cases.

Each test case begins with four integers $N$ , $M$ , $K$ , $C$ ( $1 \leq N, M \leq 100$ ; $1 \leq K \leq 10$ ; $1 \leq C \leq 25$ ).

The next $N$ lines list the names of the base ingredients.

The following $M$ lines describe the recipes, each in the format:

<product> = <ingredient 1> (q1), <ingredient 2> (q2), ..., <ingredient k> (qk); brew for <d> minutes

$1 \leq k \leq 10$
Each ingredient name consists of lowercase Latin letters, apostrophes ('), and spaces.
Quantities are integers between 1 and 10.
$1 \leq d \leq 25$
At least one recipe produces witch's brew.
It is guaranteed that there are no cyclical recipe dependencies: if product $A$ can be used directly or indirectly to obtain product $B$ , there will be no way to directly or indirectly use $B$ to obtain product $A$ .

The last $K$ lines contain names of the toxic products.

It is guaranteed that the total time required does not exceed $1 0^{15}$ .

Output

For each test case $i$ , output a single line Case #i: num where num is the minimum time to brew one unit of witch's brew.

Example

Input

2
3 3 2 2
wool of bat
eye of newt
owlet's wing
witch's brew = wool of bat (2), eye of newt (1), owlet's wing (3); brew for 25 minutes
witch's brew = sadness elixir (2); brew for 6 minutes
sadness elixir = eye of newt (5); brew for 5 minutes
sadness elixir
witch's brew
1 3 2 10
nightshade
witch's brew = sadness elixir (2); brew for 1 minutes
sadness elixir = woe elixir (2); brew for 2 minutes
woe elixir = nightshade (1); brew for 3 minutes
woe elixir
sadness elixir

Output

Case #1: 18
Case #2: 37

Explanation

Case 1.

Both sadness elixir and witch's brew are toxic products, and the witch has to spend 2 minutes cleaning the cauldron if she wants to brew something else after either of them. The recipes look as follows:

Using the first recipe, brewing witch's brew directly from base ingredients takes 25 minutes.
Using the second recipe, we first need 2 units of sadness elixir. The witch can prepare them in 10 minutes, then spend 2 minutes cleaning the cauldron, and then brew witch's brew for another 6 minutes. Note that there is no need to clean the cauldron after the last brewing session, even though witch's brew is toxic.

Thus the optimal method requires 18 minutes.

Case 2.

witch's brew requires 2 units of sadness elixir, which in turn requires 2 units of woe elixir. Both sadness elixir and woe elixir are toxic.

An optimal way to obtain witch's brew is to prepare 4 units of woe elixir first, which takes 12 minutes. Then the witch spends 10 minutes cleaning the cauldron. Then she can prepare 2 units of sadness elixir in 4 minutes. Then she has to clean the cauldron again, and then brew the final product in 1 minute.