After years of research and development your new product, the iTone 16, is ready to be manufactured.

The iTone 16 must be assembled in a certain order, e.g. first the speaker is installed, then the camera, and finally the screen. Various different manufacturers produce and install the components that it needs, and these may cost different amounts. You can't necessarily always choose the cheapest manufacturer for each component though, as some different manufacturer's components may not be compatible with each other.

After sussing out how much different companies cost and their compatabilites, can you find out what the cheapest combination of manufacturers is to produce the product?

Input

The first line consists of an integer ~n~ ~(2 \leq n \leq 100)~, the number of steps in the manufacturing process.

The next ~n~ sections are for each step in the manufacturing process, in the order the steps must be completed. They are as follows:

• The first line contains an integer ~m~ ~(1 \leq m \leq 100)~, the number of manufacturers there are for this step
• The next ~m~ lines contain a string ~N~ and an integer ~c~ — the manufacturer name and the cost of using this manufacturer. ~N~ consists of alphanumeric characters, underscores, and hyphens, and is not longer than 100 characters. The cost of a manufacturer is at least ~1~, and at most ~10^5~. Each manufacturer makes only one type of part, and that part is used in only one specific stage of production.

The next line consists of an integer ~q~, the number of incompatabilities between pairs of manufacturers. The number of incompatabilities is at least ~0~, and at most the number of adjacent manufacturers in each step.

The next ~q~ lines consists of 2 strings ~a~ and ~b~, the names of 2 manufacturers which are incompatible. Compatabilities will only ever be between manufacturers in directly adjacent steps. For example, a manufacturer m1 in the second step will only ever have incompatabilities with manufacturers that produce for the first step, and those that can produce for the third step.

Output

Output a single integer, the lowest cost to go through all manufacturing steps.

It is guaranteed that there is at least one way to pick manufacturers and successfully manufacture the product.

Example

Input 1

3
2
a 10
b 12
2
c 2
d 4
2
e 3
f 10
4
a c
b d
c f
d f

Output 1

17

For the first step, we will take manufacturer b. For the second, we take c. For the last step, we take e.