Суперагентська страва#9054

Суперагентська страва

1 секунда

128 мегабайтів

Легка

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

У Джонні є список з $n$ інгредієнтів, необхідних для приготування страви. Деякі з них можна купити в магазині, інші — приготувати з наявних інгредієнтів, а деякі можна як купити, так і приготувати. Джонні підрахував, що $m$ інгредієнтів доступні в магазині, а $k$ можна приготувати. У магазині інгредієнти продаються поштучно, і ціна вказана за одиницю. Джонні потрібно визначити, яку мінімальну суму він може витратити, щоб купити всі необхідні інгредієнти і приготувати страву.

Часу на підрахунки у Джонні немає, адже він готується до нового завдання, тому він звернувся до вас за допомогою. Допоможіть йому знайти мінімальну суму, яку потрібно витратити, або повідомте, якщо приготувати страву неможливо.

Вхідні дані

У першому рядку міститься число $n$ ( $1 \leq n \leq 100$ 1 \le n \le 100) — кількість інгредієнтів, необхідних для приготування страви.

У наступному рядку записані $n$ назв інгредієнтів $s_{i}$ s_i ( $1 \leq ∣ s_{i} ∣ \leq 20$ 1 \le |s_i| \le 20), кожна з яких складається з малих латинських літер і символів підкреслення. У третьому рядку міститься число $m$ ( $1 \leq m \leq 100$ 1 \le m \le 100) — кількість інгредієнтів, які можна купити в магазині.

У $i$ -му з наступних $m$ рядків міститься назва інгредієнта, а потім через пробіл його ціна $a_{i}$ a_i ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \le a_i \le 10^9). Гарантується, що ціна за один інгредієнт вказана не більше одного разу.

Після цього, у наступному рядку записано число $k$ ( $0 \leq k \leq 99$ 0 \le k \le 99) — кількість інгредієнтів, які можна приготувати з інших інгредієнтів.

У $j$ -му з наступних $k$ рядків спочатку записано число $c_{j}$ c_j ( $1 \leq c_{j} \leq 99$ 1 \le c_j \le 99), а потім $c_{j} + 1$ c_j + 1 назв інгредієнтів, що означає, що одну штуку інгредієнта, записаного першим, можна приготувати, взявши по одній штуці кожного з інгредієнтів, записаних після нього. Усі $c_{j}$ c_j інгредієнтів попарно різні. Грошей за виконання цієї дії Інгліш не платить. Гарантується, що у одного інгредієнта може бути не більше одного рецепта.

Гарантується, що сумарна кількість різних інгредієнтів в одному тесті не перевищує $100$ . Також гарантується, що якщо інгредієнт $A$ можна приготувати з інгредієнта $B$ (у сукупності з ще кількома інгредієнтами), то інгредієнт $B$ не можна приготувати з $A$ , а також усіх інгредієнтів, у рецепті яких бере участь $A$ або приготовані з нього інгредієнти.

Вихідні дані

Виведіть мінімальну суму, яку може витратити агент Джонні Інгліш для приготування своєї страви, або $- 1$ , якщо це неможливо.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі onion можна купити за $11$ умовних одиниць, pepper можна приготувати з pepper_red, який можна купити за $5$ у.о., tomato_paste можна зробити з tomato за $20$ у.о., mayonnaise купити за $40$ у.о.

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

У третьому прикладі a не можна ні купити, ні приготувати (тому що інгредієнт d не можна купити), тому страву приготувати неможливо.