eolymp
bolt
Try our new interface for solving problems
Problems

Super agent dish

Super agent dish

Time limit 1 second
Memory limit 128 MiB

In his free time from adventures and assignments, Agent Johnny English loves to cook. Today he decided to cook his signature super-agent dish, according to his signature recipe. However, even cooking for him is not an easy task, because he categorically does not want to spend a single extra cent.

English has a list of n ingredients needed to prepare the desired dish. Some can be bought at the store, some can be made from different ingredients, and some can be bought and cooked. The agent figured that m of his ingredients are for sale in the store, and k of them can be made from others. In the store, all ingredients are sold by the piece, and the price is also indicated for one piece. English urgently needs to understand what is the minimum amount of money he can spend in order to go to the store, buy all the necessary ingredients, and then cook a super-Gentile dish from them.

Johnny, of course, does not have time for calculations, since he needs to prepare for a new task, so he asked you to cope with this task. Help him to find the minimum amount he needs to spend to cook a super-agent dish, or tell him that it is impossible to cook a dish.

Input data

The first line contains the number n (1n100) - the number of ingredients required to prepare a super-agent dish.

The next line contains n names of these ingredients s[i] (1 ≤ |s[i]| ≤ 20), each of which consists of lowercase Latin letters and underscore characters. The third line contains the number m (1m100) - the number of ingredients that can be bought at the store.

The i - th of the following m lines contains the name of the ingredient, and then its price separated by a space is a[i] (1a[i]10^9). It is guaranteed that the price for one ingredient is quoted no more than once.

After that, the next line contains the number k (0k99) - the number of ingredients that can be prepared from other ingredients.

The j - th of the following k lines first contains the number c[j] (1c[j]99), and then c[j] + 1 ingredient names, which means that one item of the ingredient listed first can be prepared by taking one of each of the ingredients listed after it. All the c[j] ingredients are pairwise different. English does not pay money for this action. It is guaranteed that one ingredient can have at most one recipe.

It is guaranteed that the total amount of different ingredients in one dough does not exceed 100. It is also guaranteed that if ingredient A can be made from ingredient B (in combination with a few more ingredients), then ingredient B cannot be made from A as well as all ingredients, in the recipe which includes A or ingredients made from it.

Output data

Print the minimum amount that agent Johnny English can spend to cook his super-agent dish, or -1 if this is impossible.

Example

In the first example onion can be bought for 11 y.e., pepper can be made frompepper_red, that can be bought for 5 у.е., tomato_paste can be made from tomato for 20 у.е., mayonnaise can be bought for 40 у.е.

In the second example a and b can be bought for 10 y.e., c can be made from e and f for 5 + 4 = 9 у.е.

In the third example, a cannot be bought or cooked (because the d ingredient cannot be bought), so the super-agent dish cannot be cooked.

Examples

Input example #1
4
onion pepper tomato_paste mayonnaise
6
onion 11
pepper_black 3
pepper_red 5
mayonnaise 30
tomato_paste 40
tomato 20
2
1 pepper pepper_red
1 tomato_paste tomato
Output example #1
66
Input example #2
3
a b c
5
a 10
b 10
c 10
e 5
f 4
3
2 a b d
2 c e f
2 b c f
Output example #2
29
Input example #3
3
a b c
4
b 10
c 10
e 5
f 4
3
2 a b d
2 c e f
2 b c f
Output example #3
-1
Source 2018 Цикл Интернет-олимпиад для школьников, первая командная олимпиада сезона, October 14, Problem C