Ограничение по времени: 2.000 секунд
Ограничение по памяти: 100.000 мегабайт
В свободное от работы время, Сергей очень любит готовить.
Сегодня он решил приготовить свое фирменное блюдо, по своему фирменному рецепту. Однако, год был не простой, поэтому Сергей не хочет тратить на приготовление блюда ни одного лишнего рубля.
У Сергея есть список из n ингредиентов, необходимых для приготовления желанного блюда. Некоторые из них можно купить в магазине, некоторые приготовить из других ингредиентов, а некоторые можно и купить, и приготовить. Сергей посчитал, что m из его ингредиентов продается в магазине, а еще k из них можно приготовить из других. В магазине все ингредиенты продаются поштучно, и цена также указана за одну штуку. Сергею срочно нужно понять, какое минимальное количество денег он может потратить, чтобы сходить в магазин, купить все необходимые ингредиенты, а после этого приготовить из них блюдо.
Времени на подсчеты у Сергея, конечно же, нет, поэтому с этой задачей он попросил справиться вас. Помогите ему — найдите минимальную сумму, которую ему надо потратить, чтобы приготовить блюдо, или скажите, что приготовить блюдо невозможно.
В первой строке содержится число n — количество ингредиентов, необходимых для приготовления блюда (1 ≤ n ≤ 100).
В следующей строке через пробел записаны n названий этих ингредиентов si, каждое из которых состоит из строчных латинских букв и символов подчеркивания — _ (1 ≤ |si| ≤ 20).
В третьей строке содержится число m — количество ингредиентов, которые можно купить в магазине (1 ≤ m ≤ 100).
В i-й из следующих m строк содержится название ингредиента, а затем через пробел его цена ai (1 ≤ ai ≤ 109). Гарантируется, что цена за один ингредиент указана не более одного раза.
После этого, в следующей строке записано число k — количество ингредиентов, которые можно приготовить из других ингредиентов (0 ≤ k ≤ 99).
В j-й из следующих k строк сначала записано число cj, а затем cj + 1 названий ингредиентов, что означает, что одну штуку ингредиента, записанного первым, можно приготовить, взяв по одной штуке каждого из ингредиентов, записанных после него (1 ≤ cj ≤ 99). Все cj ингредиентов попарно различны. Денег за выполнение этого действия Сергей не платит. Гарантируется, что у одного ингредиента может быть не более одного рецепта.
Гарантируется, что суммарное количество различных ингредиентов в одном тесте не превосходит 100. Также гарантируется, что если ингредиент A можно приготовить из ингредиента B (в совокупности с еще несколькими ингредиентами), то ингредиент B нельзя приготовить из A, а также всех ингредиентов, в рецепте которых участвует A или приготовленные из него ингредиенты.
В единственной строке выведите минимальную сумму, которую может потратить Сергей для приготовления своего блюда, или -1, если сделать это невозможно.
| input | output |
|---|---|
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 нельзя купить), поэтому блюдо приготовить нельзя.