问题文

高桥君从妹妹那里收到了一件木制玩具作为生日礼物。

这个木制玩具由 $N$ 个球和 $N-1$ 条节构成。每个球都被编号为 $1$ 到 $N$，每个节都被编号为 $1$ 到 $N-1$。

$N-1$ 条节连接了两个不同的球，它们都从编号较大的球指向编号较小的球。另外，除了球 $1$ 以外的任何球，都有一个连接到编号较小的球的节。

每个球可以存储一个整数。一开始，球 $i (1 ≦ i ≦ N)$ 中存储了整数 $s_i$。

高桥君决定与妹妹一起，在手中拿着的 $M$ 个整数上玩木制玩具游戏。

游戏的目标是使得木制玩具中每个球中存储的整数之和尽可能大。

高桥君重复以下步骤 $M$ 次：

1. 获取一个手中的整数。第 $i$ 步获取的整数是 $t_i$。
2. 执行以下操作之一：

• 什么都不做，将整数 $t_i$ 丢弃。
• 选择木制玩具中的一个球，将整数 $t_i$ 放置在该球中。

当球 $j (1 ≦ j ≦ N)$ 接收到一个整数时，执行以下动作：

• 当 $j = 1$ 时，球 $1$ 丢弃原来存储的整数，并将接收到的整数存储在球 $1$ 中。
• 当 $j ≧ 2$ 时，球 $j$ 将原来存储的整数放置在连接到球 $j$ 的节的目标球上，并将接收到的整数存储在球 $j$ 中。

直到木制玩具不再变化，高桥君和妹妹才能继续下一步。

请计算最终可以得到的木制玩具中所有球中存储的整数之和的最大值。

输入

从标准输入中按以下格式给出输入。

$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$ 行描述了初始时每个球中的整数。其中第 $i$ 行（$1 ≦ i ≦ N$）包含一个整数 $s_i (1 ≦ s_i ≦ 1,000,000,000)$，表示球 $i$ 中最初存储的整数。
• 第 $N+2$ 行到第 $2N$ 行描述了每个节的信息。其中第 $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$ 行到第 $2N+M+1$ 行描述了手中拿着的整数。其中第 $i$ 行（$1 ≦ i ≦ M$）包含一个整数 $t_i (1 ≦ t_i ≦ 1,000,000,000)$，表示第 $i$ 步获取的整数。

部分分

本问题设置了部分分。

• 如果能在数据集 $1$ 中满足 $N ≦ 7$ 和 $M ≦ 8$ 的条件下给出正确答案，将获得 $10$ 分。
• 如果能在数据集 $2$ 中满足 $N ≦ 16$ 的条件下给出正确答案，将额外获得 $20$ 分。
• 如果能在无附加约束的数据集 $3$ 中给出正确答案，将额外获得 $70$ 分。

输出

请输出最终能够得到的木制玩具中所有球中存储的整数之和的最大值。输出应该以一行结束，包含一个换行符。

示例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

输出1

40

按以下步骤操作：

1. 取出整数 $2$。不对木制玩具执行任何操作。
2. 取出整数 $8$。将它放置在木制玩具的球 $4$ 中。
3. 取出整数 $1$。不对木制玩具执行任何操作。
4. 取出整数 $3$。不对木制玩具执行任何操作。 5