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。

相关问题

WishingBone's Room Plan

"WishingBone's Room Plan"是一道图论题目，需要使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。题目描述如下：

题目描述：

WishingBone 喜欢高耸的大楼，这次他要去参观一栋大楼。这栋大楼有n个房间，房间之间有m条通道连接。WishingBone 想知道从任意一个房间出发，最多可以到达多少个房间以及可以到达哪些房间。

输入格式：

第一行包含两个整数n和m，表示房间数和通道数。

接下来m行，每行包含两个整数a和b，表示房间a和房间b之间有一条通道。

输出格式：

输出n行，每行包含两个整数，第i行表示从第i个房间出发，最多可以到达多少个房间以及可以到达哪些房间。其中，第一个数表示最多可以到达的房间数，第二个数表示可以到达的房间编号，按照从小到大的顺序输出。

解题思路：

可以使用DFS或BFS来解决本题。以DFS为例，具体实现步骤如下：

1. 构建邻接表，表示房间之间的通道关系。

2. 初始化visited数组，表示每个房间是否被访问过。

3. 对于每个房间i，进行DFS遍历，记录可以到达的房间数和可以到达的房间编号。

4. DFS遍历过程中，对于当前房间i，将visited[i]标记为已访问，并遍历与该房间相邻的未访问过的房间j。对于每个相邻房间j，递归进行DFS遍历。

5. 当遍历完所有相邻的房间后，将visited[i]重置为未访问。

6. 对于每个房间i，输出可以到达的房间数和可以到达的房间编号，按照从小到大的顺序输出。

需要注意的是，对于本题，DFS和BFS的实现思路是一样的，只是遍历顺序不同。DFS是采用深度优先的方式遍历，而BFS是采用广度优先的方式遍历。