N개의 정점으로 이루어진 트리 A와 B가 주어진다. 두 트리의 정점은 0번부터 N-1번까지 번호가 매겨져 있다.</p>

0부터 N-1까지 각 정수에는 점수가 배정되어져 있다. 점수는 정수이며, i의 점수는 s[i]로 나타낸다.

아래와 같은 조건을 갖는 {0, 1, ..., N-1}의 부분 집합 S를 선택하는 프로그램을 작성하시오.

• 트리 A에서 S에 포함되어 있는 노드는 연결된 서브 그래프를 이루어야 한다.
• 트리 B에서 S에 포함되어 있는 노드는 연결된 서브 그래프를 이루어야 한다.

가능한 부분 집합 S중에서, 점수의 합이 최대가 되는 것을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)</p>

둘째 줄부터 N-1개의 줄에는 트리 A를 이루는 간선 a, b가 주어진다.

다음 N-1개의 줄에는 트리 B를 이루는 간선 c, d가 주어진다.

마지막 줄에는 정수의 점수가 0부터 N-1까지 주어진다. (-1,000 ≤ 점수 ≤ 1,000)

출력 형식

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

예제 입력 1

4
0 1
0 3
1 2
0 1
0 3
3 2
1000 24 100 -200

예제 출력 1

1024

예제 입력 2

4
0 1
0 3
1 2
0 1
0 3
3 2
1000 24 100 200

예제 출력 2

1324

예제 입력 3

4
0 1
0 3
1 2
0 1
0 3
3 2
-1000 24 100 200

예제 출력 3

200

예제 입력 4

7
0 1
0 2
1 3
1 4
2 5
2 6
0 1
0 2
1 3
1 4
2 5
2 6
-3 2 2 -1 2 2 -1

예제 출력 4

5

예제 입력 5

7
0 1
0 2
1 3
1 4
2 5
2 6
0 1
0 2
0 3
0 4
0 5
0 6
-3 2 2 -1 2 2 -1

예제 출력 5

5

힌트

예제 1의 경우에 집합 {0, 1}을 선택하는 것이 점수의 합이 최대가 된다. {0, 1, 2}를 선택하면 트리 B가 연결된 서브 그래프가 아니다.