Kkung's Girlfriend Plan

Kkung wants to match the girl's taste before he approaches her. Her taste is a list of combinations, and satisfying any one combination is enough. For example, she likes a man who is intelligent, cultivated and welldressed, or a man who is a motorcycleowner and slightly rude, or simply a man who is rich.

Each condition takes a fixed amount of time to satisfy. Kkung can work on several conditions at the same time, so the time a combination needs is the largest time among the conditions in that combination. When there are several combinations, he only has to satisfy one of them.

Given the time of every condition and the list of combinations, find the minimum time needed to satisfy her.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

Each test case consists of two lines.

The first line lists the conditions, separated by commas. Each entry is a name, a colon (:), then the time. A name consists of lowercase letters a to z only and has length 1 to 20, and the time is an integer from 0 to 1000. One test case has at most 20 conditions and the names are distinct.

The second line lists the combinations she accepts. Combinations are separated by a vertical bar (|), and the conditions inside one combination are separated by an ampersand (&). There are at most 10 combinations, each combination holds at least one condition, and no condition appears twice in the same combination. Every name used in a combination is defined on the first line. The input contains no spaces.

For each test case, print the minimum time needed to satisfy her on its own line.

Read the second line as (combination 1) | (combination 2) | (combination 3).