Problem Description

Takahashi received a toy tree as a birthday present from his sister.

The toy tree consists of $ N $ balls and $ N-1 $ branches. Each ball is numbered from $ 1 $ to $ N $, and each branch is numbered from $ 1 $ to $ N-1 $.

The $ N-1 $ branches connect different pairs of balls, and they are directed from the ball with the larger number to the ball with the smaller number. Additionally, for any ball other than ball $ 1 $, there is a branch directed from that ball to another ball with a smaller number.

Each ball can store exactly one integer. Initially, ball $i\ (1\ ≦\ i≦\ N)$ contains the integer $ s_i $.

Takahashi decided to play a game with his sister using the $ M $ integers they have.

The goal of the game is to maximize the sum of the integers stored in the balls of the toy tree.

Takahashi will perform the following steps $ M $ times:

1. Take out one integer from the ones they have. The integer taken out in the $i\ (1\ ≦\ i\ ≦\ M)$th step is $ t_i $.
2. Perform one of the following operations:

• Do nothing with the toy tree and discard the integer $ t_i $.
• Choose one ball from the toy tree and place the integer $ t_i $ on it.

When an integer is placed on ball $j\ (1\ ≦\ j\ ≦\ N)$, the following actions occur:

• If $j\ =\ 1$, ball $ 1 $ discards the integer it originally stored and stores the integer placed on it.
• If $j\ ≧\ 2$, ball $ j $ moves the integer it originally stored to the ball at the destination of the branch exiting from ball $ j $, and then stores the integer placed on it.

Takahashi and his sister cannot proceed to the next step until the changes in the toy tree have stopped.

Determine the maximum possible sum of the integers stored in the balls of the toy tree after all steps are completed.

Input Format

The input is given from the standard input in the following format:

$ N $ $ s_1 $ $ s_2 $ : $ s_N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_{N-1} $ $ b_{N-1} $ $ M $ $ t_1 $ $ t_2 $ : $ t_M $

• The first line contains an integer $N\ (2\ ≦\ N\ ≦\ 5,000)$, representing the number of balls in the toy tree.
• The next $ N $ lines contain information about the integers initially stored in the balls. The $i\ (1\ ≦\ i\ ≦\ N)$th line contains an integer $s_i\ (1\ ≦\ s_i\ ≦\ 1,000,000,000)$, indicating that ball $ i $ initially contains the integer $ s_i $.
• The next $ N-1 $ lines contain information about the branches. The $i\ (1\ ≦\ i\ ≦\ N-1)$th line contains two integers $a_i,\ b_i\ (1\ ≦\ a_i\ ＜\ b_i\ ≦\ N)$ separated by a space, indicating that there is a branch from ball $ b_i $ to ball $ a_i $.
• The $ 2N+1 $th line contains an integer $M\ (1\ ≦\ M\ ≦\ 5,000)$, representing the number of integers they have.
• The next $ M $ lines contain information about the integers they have. The $i\ (1\ ≦\ i\ ≦\ M)$th line contains an integer $t_i\ (1\ ≦\ t_i\ ≦\ 1,000,000,000)$, indicating that the integer $ t_i $ is taken out in the $ i $th step.

Output Format

Output the maximum possible sum of the integers stored in the balls of the toy tree after all steps are completed. End the output with a newline.

Sample Input and Output

Sample Input #1

7
4
7
5
1
5
2
4
1 2
1 3
1 4
2 5
2 6
6 7
8
2
8
1
3
6
3
7
5

Sample Output #1

40

Sample Input #2

6
21
5
5
5
5
5
1 2
1 3
1 4
1 5
1 6
5
8
8
8
8
8

Sample Output #2

46

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset $ 1 $ where $N\ ≦\ 7$ and $M\ ≦\ 8$, you will get $ 10 $ points.
• If you solve the dataset $ 2 $ where $N\ ≦\ 16$, you will get an additional $ 20 $ points.
• If you solve the dataset $ 3 $ without additional constraints, you will get an additional $ 70 $ points.

见题面 Input 部分

见题面 Output 部分