점수의 합

정점이 $N$개인 트리 $A$와 $B$가 주어진다. 두 트리 모두 정점에 0번부터 $N-1$번까지 번호가 붙어 있고, $i$번 정점의 점수는 $s_i$이다. 점수는 정수이며 음수일 수도 있다.

다음 두 조건을 모두 만족하는, 공집합이 아닌 부분 집합 $S \subseteq \{0, 1, \dots, N-1\}$을 고른다.

• 트리 $A$에서 $S$에 속한 정점만 남기면 연결된 부분 그래프가 된다.
• 트리 $B$에서 $S$에 속한 정점만 남기면 연결된 부분 그래프가 된다.

이런 $S$ 중에서 점수의 합 $\sum_{i \in S} s_i$의 최댓값을 구하는 프로그램을 작성하시오.

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

다음 $N-1$개의 줄에는 트리 $A$의 간선이 한 줄에 하나씩, 두 정수 $a$와 $b$로 주어진다. ($0 \le a, b \le N-1$, $a \ne b$)

이어지는 $N-1$개의 줄에는 같은 형식으로 트리 $B$의 간선이 주어진다.

마지막 줄에는 정수 $N$개 $s_0, s_1, \dots, s_{N-1}$이 공백으로 구분되어 주어진다. ($-1000 \le s_i \le 1000$)

입력으로 주어지는 두 그래프는 모두 트리이다.

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

첫 번째 예제에서는 $\{0, 1\}$을 고를 때 점수의 합이 최대가 된다. $\{0, 1, 2\}$를 고르면 트리 $B$에서 연결된 부분 그래프가 되지 않는다.