지붕 색칠하기

N개의 집으로 이루어진 작은 마을이 있다. 집들 사이에는 길이 나 있으며, 주어진 길만 이용해도 어떤 집에서든 다른 모든 집으로 이동할 수 있다. 또한 이 길들은 사이클을 만들지 않으므로 전체 구조는 트리이다.

각 집의 지붕을 한 가지 색으로 칠하려고 한다. 길로 직접 연결된 두 집은 서로 다른 지붕 색을 가져야 한다.

집들 사이의 길 정보와 색깔별 페인트 비용이 주어진다. 조건을 만족하도록 모든 지붕을 칠하는 최소 비용을 구하라.

첫째 줄에 집의 수 N이 주어진다. 다음 N-1개의 줄에는 길의 정보가 하나씩 주어진다. 각 줄에는 1 이상 N 이하인 서로 다른 두 자연수 A, B가 주어지며, A번 집과 B번 집이 직접 연결되어 있음을 의미한다.

그다음 줄에는 페인트 색의 수 M이 주어진다. 마지막 줄에는 M개의 자연수가 주어지며, i번째 수는 i번째 색으로 집 한 채의 지붕을 칠하는 비용이다. 모든 비용은 10,000 이하이다.

지붕을 칠하는 데 필요한 최소 비용을 출력한다.

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