Painting Roofs

There is a small village with N houses. Roads connect pairs of houses. Using only the given roads, every house can be reached from any other house, and the road network has no cycle; therefore it forms a tree.

Each house's roof must be painted with one color. Two houses directly connected by a road must have different roof colors.

Given the roads between houses and the cost of each paint color, compute the minimum total cost needed to paint all roofs while satisfying the condition.

The first line contains the number of houses, N. The next N-1 lines each contain one road. Each road is described by two different integers A and B between 1 and N, meaning that house A and house B are directly connected.

The next line contains the number of paint colors, M. The final line contains M natural numbers; the i-th number is the cost of painting one house's roof with color i. Every cost is at most 10,000.

Print the minimum total cost required to paint the roofs.

• 1 <= N <= 10,000
• 1 <= M <= 10,000