收集瓶盖

题目描述:

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!

题意：Petrov收集了一些瓶盖，但是没有收集完，所以还需购买一些。

输入格式:

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 ≤ 101) — 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.

第一行一个数N表示瓶盖的种类数量。

接下来N行每行一个数表示第i种瓶盖在店里买需要的钱。

接下来一行一个数M，表示有M种优惠方案。

接下来M行，每行首先有两个数，分别表示当前优惠方案的价格和所出售瓶盖的种数，然后依次给出每种瓶盖的编号（范围保证在1到N并且不重复）。

最后一行首先一个数，表示Petrov想要买的瓶盖种数，然后依次给出每种瓶盖的编号（范围保证在1到N并且不重复）。

输出格式:

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

输出一个数，表示能买到所有Petrov想要瓶盖的最小价钱（当然每种瓶盖可以购买多次）。

样例输入:

4
10
11
12
13
3
17 2 1 3
25 3 2 3 4
15 2 3 4
3 1 3 4

样例输出:

25

提示:

1<=N<=20

1<=M<=101

时间限制: 1000ms
空间限制: 256MB

---

来源: Ural P1326