ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2004 Round 2

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Bottle Taps

Time limit: 3.0 second
Memory limit: 64 MB
Programmer Petrov has a hobby to collect beer-bottle taps. There’s nothing unusual — he knows hundreds of programmers that like beer. And they collect taps, too. Not everyone, but some of them.
Frankly speaking, he has bought a part of his collection. But unfortunately he hasn’t got some rare taps to complete his collection. He has found some programmers over the Internet that are ready to sell him these taps. Some of the programmers sell the taps in sets with big discounts.
It’s left to find an optimal offer. Petrov can explain to his wife why he is to store the taps but he won’t be able to prove why he is to spend money for the collection. So he is to buy the taps as cheap as possible.
Petrov has written down all the variants and has started thinking. There’s no way to find out the solution of the problem without a program!


The first line contains an integer N, an amount of available taps (1 ≤ N ≤ 20). The following N lines contain prices of bottles with the taps if one buys them in stores. The next line contains an integer M (0 ≤ M ≤ 100) — an amount of offers to sell the taps. The following M lines describe the sets. The first number of each line is the price of the set and the second one is the amount of taps in the set. Then there are numbers of the taps in the set (each number lies in the range from 1 to N). The numbers in a set are unique. All the prices are positive integers and do not exceed 1000. The last line begins with the amount of taps that Petrov plans to buy. Then their numbers follow separated by spaces. These numbers are unique, too.


Output the minimal sum of money that Petrov should spend on obtaining the necessary taps.


17 2 1 3
25 3 2 3 4
15 2 3 4
3 1 3 4
Problem Author: Idea: Evgeny Kobzev, prepared by Pavel Atnashev, Alexander Mironenko
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004
To submit the solution for this problem go to the Problem set: 1326. Bottle Taps