ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2004 Тур II

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Крышки

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
У программиста Петрова есть хобби — собирать крышки от пивных бутылок. Ничего странного, он знает еще с сотню программистов, которые очень уважают пиво. Да, они тоже собирают крышки. Не все из них, конечно, но некоторые.
Если честно, то часть своих крышек он просто купил, уже без бутылок. Да, это не совсем спортивно, зато коллекция теперь более солидная. Одна вот беда — не хватает ему для полноты коллекции еще нескольких редких крышек. Он даже нашел в Интернете программистов, которые согласны продать их ему. Некоторые даже продают крышки сразу наборами, с большой скидкой. Почему продают, да еще со скидкой? А вы попробуйте объяснить жене, какая польза от пивных крышек. Она же не программист.
Осталось выбрать оптимальные предложения. Если объяснить жене зачем надо хранить крышки еще возможно, то почему на них надо тратить деньги — точно не поймет. Поэтому надо купить как можно дешевле.
Петров выписал на бумажку все варианты и задумался. Купить сразу все не получится, никаких денег не хватит. Тогда надо купить самые необходимые, но подешевле. Да уж, без программы тут не обойдешься…

Исходные данные

В первой строке записано число N — количество недостающих Петрову крышек (1 ≤ N ≤ 20). Далее идет N строк — цена, за которую можно купить эту крышку, если покупать ее отдельно. В следующей строке стоит число M (0 ≤ M ≤ 100) — количество предложений по продаже наборов, содержащих нужные ему крышки. Далее идет M строк описывающих эти наборы. В каждой строке первое число — цена набора, второе — количество крышек в наборе, далее перечислены номера крышек (каждый номер от 1 до N), которые в этот набор входят. Номера в наборе не повторяются. Все цены — положительные числа, не превосходящие 1000. В последней строке перечислен минимальный набор крышек, который Петров намерен купить в любом случае.

Результат

Выведите минимальную сумму, необходимую Петрову, чтобы купить все крышки из приведённого в последней строке набора.

Пример

исходные данныерезультат
4
10
11
12
13
3
17 2 1 3
25 3 2 3 4
15 2 3 4
3 1 3 4
25
Автор задачи: Идея — Евгений Кобзев, подготовка — Павел Атнашев и Александр Мироненко
Источник задачи: VIII Командный студенческий чемпионат Урала по программированию. Екатеринбург, 11-16 марта 2004 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1326. Крышки