0 人解决，2 人已尝试。
0 份提交通过，共有 13 份提交。
9.9 EMB 奖励。
单点时限: 20.0 sec
内存限制: 256 MB
You are a hero of a role playing game, asked by the king to defeat monsters threating people’s life.
You have been making a long journey with your colleagues, and you are now in the town closest to the final dungeon where the head of monsters dwells. You have heard from people that the head monster hits with his strong arms, casts powerful spells, and has many special abilities, and your party would be easily killed off without powerful equipments due to severe damages. Thus you need to prepare the equipments.
On the other hand, you have a number of magical spheres collected during the journey. Those spheres are not useful themselves, but they can be turned into special items by a spell of reaction. You can obtain some amount of money by selling those special items to shops in the town, then buy the equipments by that money.
The spell of reaction works as follows. Each sphere has a color, and either positive attribute or negative attribute. You choose one sphere with positive attribute and another with negative attribute, and you cast the spell to the two spheres. Then the spheres will make reaction to have a set of special items produced. Those spheres will disappear after the reaction. The set of items you will obtain solely depends on the colors of the two spheres. You can cast the spell as many as you want, but of course you cannot cast the spell to spheres that have disappeared. Also, not all pairs of colors of spheres make reaction.
It is natural that you want to obtain money as much as possible. So you should choose carefully the pairs of spheres before casting the spell. On the other hand, you should be an excellent programmer, so it should be an easy task to write a program that finds the best way using your computer.
Your task is now clear - write a program and get ready for the battle with the head monster!
The input is a sequence of datasets. Each dataset is formatted as follows:
The first line contains two integers N- and N+, which are the numbers of different colors of spheres with negative and positive attributes, respectively. The rest of the dataset is divided into three parts.
The first part describes the number of available spheres. This part has the following format:
K1- K2- … KN--
K1+ K2+ … KN++
Ki- is the number of spheres of the i-th color with negative attribute, and Ki+ is the number of spheres of the i-th color with positive attribute.
The second part contains the definition of items. This part is formatted as follows:
M
A1 P1
…
AM PM
Here, M is the number of items that can be produced. Each of the following M lines contains a string A1 and an integer P1, which are the name and the selling price of the i-th item respectively.
The last part gives the details of reactions. This part has the following format:
L
I1- I1+ NJ1 J1,1 … J1,NJ1
…
IL- IL+ NJL JL,1 … JL,NJL
The first line contains an integer L, which is the number of pairs of colors of spheres that can make reaction. Each of the next L lines starts with two integers Ii- and Ii+, which denote the colors of negative and positive spheres respectively. The next integer NJi is the number of items produced by reaction between spheres Ii- and Ii+. The line is then followed by NJi strings, each of which is an item name.
You may assume all the following: 1 ≤ N-, N+ ≤ 100; 1 ≤ Ki-, Ki+ ≤ 100; 1 ≤ M ≤ 100; 1 ≤ Pi ≤ 100; 1 ≤ L ≤ 100; 1 ≤ NJi ≤ 10. You may also assume that an item name consists only of alphanumeric characters and the length of the name does not exceed ten.
The end of input is represented by a line with two zeros. This line is not part of any dataset.
For each dataset, print a line that contains the maximum possible total selling price.
2 2 1 1 1 1 4 A 10 B 20 C 30 D 40 4 1 1 3 A A A 1 2 2 B C 2 1 1 D 2 2 3 A A B 2 2 1 2 2 1 3 Scroll 50 Bastard 100 Heal100 10 3 1 1 1 Scroll 2 1 1 Bastard 2 2 1 Heal100 0 0
90 200
0 人解决，2 人已尝试。
0 份提交通过，共有 13 份提交。
9.9 EMB 奖励。
创建: 15 年，8 月前.
修改: 7 年，2 月前.
最后提交: 14 年前.
来源: N/A