정점의 개수가 N개인 두 트리가 주어진다. 트리의 각 노드는 0부터 N-1까지 번호가 매겨져 있다.</p>

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

집합 {0, 1, ..., N-1}의 부분 집합을 골라서 부분 집합에 포함되어 있는 정점의 점수의 합의 최댓값을 구하는 프로그램을 작성하시오. 이때, 다음과 같은 두 조건을 만족해야 한다.

• 첫 번째 트리에서 부분 집합에 포함되어 있는 정점끼리 연결 서브 그래프를 만들어야 한다.
• 두 번째 트리에서 부분 집합에 포함되어 있는 정점끼리 연결 서브 그래프를 만들어야 한다.

두 조건을 만족시키는 부분 집합 중에서 정점의 점수가 가장 큰 것을 구하는 프로그램을 작성하시오.

입력 형식

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

둘째 줄부터 N-1개 줄에는 첫 번째 트리의 간선 정보가 주어진다.

그 다음 N-1개 줄에는 두 번째 트리의 간선 정보가 주어진다.

마지막 줄에는 점수 S₀, S₁, ..., S_N-1이 주어진다. (-1,000 ≤ S_i ≤ 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

0

예제 입력 4

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

예제 출력 4

200

힌트

{0, 1}을 고르면 두 트리에서 모두 연결된 서브 그래프를 만든다. {0, 1, 2}는 두 번째 트리에서 0에서 2로 이동할 수 없다.