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.

这是一道动态规划问题。我们可以把每个菱形看做一个节点，节点之间有边相连，边的权值为两个节点对应的三角形的颜色组合。我们需要找到一条路径，使得路径上所有边的权值之和最小，且路径经过的所有节点组成的集合覆盖了所有的三角形。这可以通过最小权闭合子图来求解。具体来说，我们可以在原图上添加一个超级源点和一个超级汇点，然后把所有未被覆盖的三角形对应的节点与源点相连，把所有已经被覆盖的三角形对应的节点与汇点相连，然后在新图上求解最小权闭合子图即可。如果闭合子图不存在，则说明无法完全覆盖所有三角形，输出0。

对于每个测试用例，可以按照以下步骤求解：

1. 构建图，计算每个三角形对应的节点编号和对应的菱形编号。
2. 构建新图，添加超级源点和超级汇点，并按照上述方法连接节点和超级源点/超级汇点。
3. 在新图上求解最小权闭合子图，得到路径上所有边的权值之和。
4. 如果闭合子图不存在，则输出0；否则输出路径上所有边的权值之和。

时间复杂度为 O(n^3)，可以通过本题。