| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 33 | 7 | 7 | 25.926% |
В свободное от приключений и заданий время, агент Джонни Инглиш очень любит готовить. Сегодня он решил приготовить свое фирменное суперагентское блюдо, по своему фирменному рецепту. Однако даже приготовление еды для него --- непростое задание, ведь он категорически не хочет тратить ни одного лишнего цента.
У Инглиша есть список из $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 нельзя купить), поэтому суперагентское блюдо приготовить нельзя.