В свободное от приключений и заданий время, агент Джонни Инглиш очень любит готовить. Сегодня он решил приготовить свое фирменное суперагентское блюдо, по своему фирменному рецепту. Однако даже приготовление еды для него — непростое задание, ведь он категорически не хочет тратить ни одного лишнего цента.
У Инглиша есть список из $$$n$$$ ингредиентов, необходимых для приготовления желанного блюда. Некоторые из них можно купить в магазине, некоторые приготовить из других ингредиентов, а некоторые можно и купить, и приготовить. Агент посчитал, что $$$m$$$ из его ингредиентов продается в магазине, а еще $$$k$$$ из них можно приготовить из других. В магазине все ингредиенты продаются поштучно, и цена также указана за одну штуку. Инглишу срочно нужно понять, какое минимальное количество денег он может потратить, чтобы сходить в магазин, купить все необходимые ингредиенты, а после этого приготовить из них суперагенское блюдо.
Времени на подсчеты у Джонни, конечно же, нет, так как нужно готовиться к новому заданию, поэтому с этой задачей он попросил справиться вас. Помогите ему — найдите минимальное сумму, которую ему надо потратить, чтобы приготовить суперагентское блюдо, или скажите, что приготовить блюдо невозможно.
В первой строке содержится число $$$n$$$ — количество ингредиентов, необходимых для приготовления суперагентского блюда ($$$1 \le n \le 100$$$).
В следующей строке через пробел записаны $$$n$$$ названий этих ингредиентов $$$s_i$$$, каждое из которых состоит из строчных латинских букв и символов подчеркивания — $$$\_$$$ ($$$1 \le |s_i| \le 20$$$).
В третьей строке содержится число $$$m$$$ — количество ингредиентов, которые можно купить в магазине ($$$1 \le m \le 100$$$).
В $$$i$$$-й из следующих $$$m$$$ строк содержится название ингредиента, а затем через пробел его цена $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$). Гарантируется, что цена за один ингредиент указана не более одного раза.
После этого, в следующей строке записано число $$$k$$$ — количество ингредиентов, которые можно приготовить из других ингредиентов ($$$0 \le k \le 99$$$).
В $$$j$$$-й из следующих $$$k$$$ строк сначала записано число $$$c_j$$$, а затем $$$c_j + 1$$$ названий ингредиентов, что означает, что одну штуку ингредиента, записанного первым, можно приготовить, взяв по одной штуке каждого из ингредиентов, записанных после него ($$$1 \le c_j \le 99$$$). Все $$$c_j$$$ ингредиентов попарно различны. Денег за выполнение этого действия Инглиш не платит. Гарантируется, что у одного ингредиента может быть не более одного рецепта.
Гарантируется, что суммарное количество различных ингредиентов в одном тесте не превосходит $$$100$$$. Также гарантируется, что если ингредиент $$$A$$$ можно приготовить из ингредиента $$$B$$$ (в совокупности с еще несколькими ингредиентами), то ингредиент $$$B$$$ нельзя приготовить из $$$A$$$, а также всех ингредиентов, в рецепте которых участвует $$$A$$$ или приготовленные из него ингредиенты.
В единственной строке выведите минимальную сумму, которую может потратить агент Джонни Инглиш для приготовления своего суперагентского блюда, или -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
66
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
29
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
-1
В первом примере onion можно купить за $$$11$$$ условных единиц, pepper можно приготовить из pepper_red, который можно купить за $$$5$$$ у.е., tomato_paste можно сделать из tomato за $$$20$$$ у.е., mayonnaise купить за 40 у.е.
Во втором примере a и b можно купить за 10 у.е., c приготовить из e и f за $$$5 + 4 = 9$$$ у.е.
В третьем примере a нельзя ни купить, ни приготовить (потому что ингредиент d нельзя купить), поэтому суперагентское блюдо приготовить нельзя.