Суперагентское блюдо

시간 제한2초메모리 제한1024 MB

요약

재료마다 구매 가격과 조합 레시피가 주어질 때, 요리를 완성하는 데 드는 최소 비용을 구한다. 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그래프, DFS, 위상 정렬
정답자: 아직 제출이 없습니다

문제

В свободное от приключений и заданий время, агент Джонни Инглиш очень любит готовить. Сегодня он решил приготовить свое фирменное суперагентское блюдо, по своему фирменному рецепту. Однако даже приготовление еды для него --- непростое задание, ведь он категорически не хочет тратить ни одного лишнего цента.

У Инглиша есть список из $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, если сделать это невозможно.

힌트

В первом примере onion можно купить за $11$ условных единиц, pepper можно приготовить из pepper\_red, который можно купить за $5$ у.е., tomato\_paste можно сделать из tomato за $20$ у.е., mayonnaise купить за 40 у.е.

Во втором примере a и b можно купить за 10 у.е., c приготовить из e и f за $5 + 4 = 9$ у.е.

В третьем примере a нельзя ни купить, ни приготовить (потому что ингредиент d нельзя купить), поэтому суперагентское блюдо приготовить нельзя.

예제3

예제 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

예상 출력

예제 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

예상 출력

예제 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

예상 출력

-1