You are a hero of a role playing game, asked by the king to defeat monsters threating peoplefs 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:

N^{-}N^{+}Number of available spheresDefinition of itemsDefinition of reactions

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:

K_{1}^{-}K_{2}^{-}...K_{N-}^{-}K_{1}^{+}K_{2}^{+}...K_{N+}^{+}

*K*_{i}^{-} is the number of spheres of the *i*-th color with negative attribute, and *K*_{i}^{+} 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:

MA_{1}P_{1}...A_{M}P_{M}

Here, *M* is the number of items that can be produced. Each of the following *M* lines contains a string *A _{i}*
and an integer

The last part gives the details of reactions. This part has the following format:

LI_{1}^{-}I_{1}^{+}NJ_{1}J_{1,1}...J_{1,NJ1}...I_{L}^{-}I_{L}^{+}NJ_{L}J_{L,1}...J_{L,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 *I*_{i}^{-} and *I*^{+}, which denote the colors of negative
and positive spheres respectively. The next integer *NJ _{i}* is the number of items produced by reaction
between spheres

You may assume all the following: 1 ≤ *N*^{-}, *N*^{+} ≤ 100; 1 ≤ *K*_{i}^{-}, *K*_{i}^{+} ≤ 100; 1 ≤ *M* ≤ 100; 1 ≤ *P _{i}* ≤ 100;
1 ≤

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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2008
, Day 4, Tokyo, Japan, 2008-09-15

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/