Witch's Cauldron (part 2)

Note: this problem is similar to Witch's Cauldron (part 3), but does not involve 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.

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 two integers $N$ and $M$ ( $1 \leq N, M \leq 100$ ).

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$ .

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

1
3 3
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

Output

Case #1: 16

Explanation

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. Each takes 5 minutes, so 10 minutes in total, then another 6 minutes to combine them. Total = 16 minutes.

Thus the optimal method requires 16 minutes.