Суперагентское блюдо
В свободное от приключений и заданий время, агент Джонни Инглиш очень любит готовить. Сегодня он решил приготовить свое фирменное суперагентское блюдо, по своему фирменному рецепту. Однако даже приготовление еды для него - непростое задание, ведь он категорически не хочет тратить ни одного лишнего цента.
У Инглиша имеется список из n ингредиентов, необходимых для приготовления желанного блюда. Некоторые из них можно купить в магазине, некоторые приготовить из других ингредиентов, а некоторые можно и купить, и приготовить. Агент посчитал, что m из его ингредиентов продается в магазине, а еще k из них можно приготовить из других. В магазине все ингредиенты продаются поштучно, и цена также указана за одну штуку. Инглишу срочно нужно понять, какое минимальное количество денег он может потратить, чтобы сходить в магазин, купить все необходимые ингредиенты, а после этого приготовить из них суперагентское блюдо.
Времени на подсчеты у Джонни, конечно же, нет, так как нужно готовиться к новому заданию, поэтому с этой задачей он попросил справиться вас. Помогите ему — найдите минимальное сумму, которую ему надо потратить, чтобы приготовить суперагентское блюдо, или скажите, что приготовить блюдо невозможно.
Входные данные
В первой строке содержится число n (1 ≤ n ≤ 100) - количество ингредиентов, необходимых для приготовления суперагентского блюда.
В следующей строке записаны n названий этих ингредиентов s[i] (1 ≤ |s[i]| ≤ 20), каждое из которых состоит из строчных латинских букв и символов подчеркивания. В третьей строке содержится число m (1 ≤ m ≤ 100) - количество ингредиентов, которые можно купить в магазине.
В i-й из следующих m строк содержится название ингредиента, а затем через пробел его цена a[i] (1 ≤ a[i] ≤ 10^9). Гарантируется, что цена за один ингредиент указана не более одного раза.
После этого, в следующей строке записано число k (0 ≤ k ≤ 99) - количество ингредиентов, которые можно приготовить из других ингредиентов.
В j-й из следующих k строк сначала записано число c[j] (1 ≤ c[j] ≤ 99), а затем c[j] + 1 названий ингредиентов, что означает, что одну штуку ингредиента, записанного первым, можно приготовить, взяв по одной штуке каждого из ингредиентов, записанных после него. Все 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 нельзя купить), поэтому суперагентское блюдо приготовить нельзя.