WishingBone's Room Plan

Time Limit: 10 Seconds    Memory Limit: 32768 KB

WishingBone plans to decorate his hexagon-shaped room with unique flooring patterns. First he divides it into triangles, and colors them with different colors.

Now that he has got a satisfactory pattern, he uses small rugs to cover the floor. The rugs sold at shops are diamond-shaped; exact the shape of two adjacent triangles. He is not willing to cut any of them. Different colored rugs are labeled different price. And he does care about the price - he cares about the most expensive rugs that he should use to finish the covering.

Input

There are multiple tests, for each test:

The first line is an integer specifying the side of his room (1 <= n <= 50).

The following 2n lines with the pattern of the room, with upper-case letters denoting different colors. So there are at most 26 colors. Since the room is considerably large and sometimes needs pillars to support the ceiling, some triangles are marked with '.' rather than a letter. Such triangles are not to be covered.

The following line contains one integer m (1 <= m <= 351) - number of rugs in the shop.

The following m lines contains one type of rug (with two upper-case letters) and its price p (1 <= p <= 100000). There will not be duplicate items listed, that is, if AB is listed, BA will not appear. You may assume the number of each type to be infinite.

Output

One line for each test, the price of the most expensive rugs used. Of course, you have to minimize this value. If there is no solution to the problem, print a 0.

Sample Input

1
ABC
ABC
6
AA 1
AB 2
AC 3
BB 4
BC 5
CC 6
2
A.CAB
A.CABCA
ABCABCA
ABCAB
6
AA 1
AB 2
AC 3
BB 4
BC 5
CC 6

Sample Output

5
0

Submit

Source: ZOJ Monthly, March 2003