1814번 - 지붕 색칠하기

N개의 집들로 이루어진 작은 마을이 있다. 이 마을의 몇몇 집들 사이에는 길이 나 있는데, 이 길들을 잘 이용하면 임의의 집에서 출발하여 어느 집으로든 이동할 수 있다. 그러나 출발했던 집으로 되돌아오려 할 때, 이미 방문했던 집들 중 일부를 다시 방문하지 않고서는 방법이 없다.

이 마을을 새로 단장하면서 각 집들의 지붕을 색칠하기로 했는데, 서로를 연결하는 길을 사이에 두고 있는 두 개의 집은 다른 색깔의 지붕을 갖도록 하려 한다.

집들 사이에 나 있는 길들의 정보와, 색깔별로 페인트들의 가격이 주어졌을 때, 조건을 만족하면서 집들의 지붕을 색칠하기 위한 최소 비용을 구하는 프로그램을 작성하시오.

첫째 줄에, 마을 내의 집들의 수 N이 주어진다. 이후 N-1개의 줄에, 집들을 잇는 길의 정보가 하나씩 주어진다. 각 줄은 1이상 N이하 범위에 있는, 서로 다른 두 자연수 A, B로 구성되는데, A번 집과 B번 집 사이에 길이 나 있다는 의미이다.

N+1번째 줄에는, 페인트 종류의 수 M이 주어진다. N+2번째 줄에 주어지는 M개의 자연수는, 각 페인트별로 한 집의 지붕을 칠하기 위한 비용이다. 이들은 모두 10,000 이하이다.

첫째 줄에, 지붕의 색칠을 위한 최소 비용을 출력한다.

• 1 ≤ N ≤ 10,000
• 1 ≤ M ≤ 10,000