두 트리

정점이 $N$개인 트리 두 개가 주어진다. 두 트리 모두 정점에 $0$번부터 $N-1$번까지 번호가 붙어 있고, 같은 번호는 같은 정점을 가리킨다.

$i$번 정점의 점수는 $S_i$이다.

집합 $\{0, 1, \dots, N-1\}$의 부분 집합 중에서 다음 두 조건을 모두 만족하는 것을 고른다.

• 첫 번째 트리에서 부분 집합에 속한 정점만 남기면 연결된 부분 그래프가 된다.
• 두 번째 트리에서 부분 집합에 속한 정점만 남기면 연결된 부분 그래프가 된다.

조건을 만족하는 부분 집합의 점수 합 중 최댓값을 구하는 프로그램을 작성하시오. 공집합도 부분 집합이고 그 합은 $0$이므로, 답이 음수가 되는 일은 없다.

첫째 줄에 정점의 개수 $N$이 주어진다. ($2 \le N \le 50$)

다음 $N-1$개 줄에는 첫 번째 트리의 간선이 한 줄에 하나씩 주어진다. 각 줄에는 그 간선이 잇는 두 정점의 번호가 주어진다.

그다음 $N-1$개 줄에는 같은 형식으로 두 번째 트리의 간선이 주어진다.

마지막 줄에는 점수 $S_0, S_1, \dots, S_{N-1}$이 공백으로 구분되어 주어진다. ($-1000 \le S_i \le 1000$)

첫째 줄에 점수 합의 최댓값을 출력한다.

첫 번째 예제에서 $\{0, 1\}$은 두 트리 모두에서 연결된 부분 그래프를 이룬다. $\{0, 1, 2\}$는 그렇지 않다. 두 번째 트리에서 정점 $2$는 정점 $3$과만 이어져 있는데, 정점 $3$이 집합에 없기 때문이다.