Problem Statement

高橋君は妹から誕生日プレゼントに木のおもちゃを貰った。

木のおもちゃは $N$ 個の球と $N-1$ 本の節からなる。各球には $1$ から $N$ まで番号がつけられており、各節には $1$ から $N-1$ まで番号が付けられている。

$N-1$ 本の節は、異なる $2$ つの球を接続しており、これらはすべて番号の大きい方の球から番号の小さい方の球へと向きが付けられている。また、球 $1$ 以外のどの球からも、その球から番号の小さい別の球へと向きがつけられている節がある。

どの球もちょうど $1$ つの整数を格納することができる。最初、球 $i (1 ≦ i≦ N)$ には整数 $s_i$ が格納されている。

高橋君は妹と一緒に、手元にある $M$ 個の整数を使って木のおもちゃでゲームをすることにした。

ゲームの目的は、木のおもちゃのそれぞれの球に格納されている整数の合計ができるだけ大きくなるようにすることにした。

高橋君は $M$ 回、以下のステップを行う。

1. 手元にある整数を $1$ つ取り出す。$i (1 ≦ i ≦ M)$ 回目のステップで取り出す整数は $t_i$ である。
2. 以下のいずれかの操作を行う。

• 木のおもちゃに対して何もせず、整数 $t_i$ を捨てる。
• 木のおもちゃを構成する球から $1$ つ選び、整数 $t_i$ を置く。

球 $j (1 ≦ j ≦ N)$ は、整数が置かれたとき、以下の動作を行う。

• $j = 1$ のとき、球 $1$ は元から格納してある整数を捨て、球 $1$ に置かれた整数を格納する。
• $j ≧ 2$ のとき、球 $j$ は元から格納してある整数を、球 $j$ から出ている節の行き先となる球におき、球 $j$ に置かれた整数を格納する。

木のおもちゃの変化が止まるまで、高橋君と妹は次のステップに移動することができない。

最終的に木のおもちゃの各球に格納されている整数の合計値として考えられる最大値を求めよ。

Input

入力は以下の形式で標準入力から与えられる。

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

• $1$ 行目には、妹から貰った木のおもちゃを構成する球の個数を表す整数 $N (2 ≦ N ≦ 5,000)$ が与えられる。
• $2$ 行目から $N$ 行には、球に最初から格納されている整数に関する情報が与えられる。これら $N$ 行のうち上から $i (1 ≦ i ≦ N)$ 行目には整数 $s_i (1 ≦ s_i ≦ 1,000,000,000)$ が与えられる。これは、球 $i$ には最初に整数 $s_i$ が格納されていることを表す。
• $N+2$ 行目から $N-1$ 行には、節に関する情報が与えられる。これら $N-1$ 行のうち上から $i (1 ≦ i ≦ N-1)$ 行目には整数 $a_i, b_i (1 ≦ a_i ＜ b_i ≦ N)$ が空白区切りで与えられる。これは、球 $b_i$ から出て、球 $a_i$ に入る節があることを表す。
• $2N+1$ 行目には、手元にある整数の個数を表す整数 $M (1 ≦ M ≦ 5,000)$ が与えられる。
• $2N+2$ 行目から $M$ 行には、手元にある整数に関する情報が与えられる。これら $M$ 行のうち上から $i (1 ≦ i ≦ M)$ 行目には整数 $t_i (1 ≦ t_i ≦ 1,000,000,000)$ が与えられる。これは、$i$ 回目のステップで整数 $t_i$ を取り出すことを表す。

部分点

この問題には部分点が設定されている。

• $N ≦ 7$ かつ $M ≦ 8$ を満たすデータセット $1$ に正解した場合は、$10$ 点が与えられる。
• $N ≦ 16$ を満たすデータセット $2$ に正解した場合は、上記とは別に $20$ 点が与えられる。
• 追加制約のないデータセット $3$ に正解した場合は、上記とは別に $70$ 点が与えられる。

Output

最終的に木のおもちゃの各球に格納されている整数の合計値として考えられる最大値を $1$ 行に出力せよ。出力の末尾にも改行を入れること。