给定一棵大小为 $N$，根为 $1$ 的树，并指定树上边的方向为编号大的指向编号小的。给定树上点 $i$ 的权值为 $s_i$。

现在给定 $M$ 个操作。每个操作依次进行。对于每个操作 $i$，有参数 $t_i$，可以选择：

• 不进行操作
• 在树上任意选定一个节点 $u$ 。并对原树进行参数为 $t_i$ 的上移操作。

参数为 $t_i$ 的上移操作就是将原图中 $u$ 以及它的所有祖先（除了根）的权值向父亲节点上移一位（根节点权值被删除），然后再将 $s_u$ 设为 $t_i$。

求在经历 $M$ 次操作之后，最终整棵树的权值和最大是多少。

【输入格式】

第一行一个整数 $N$，表示树的大小。

接下来 $N$ 行，每行一个整数 $s_i$，表示 $i$ 点的权值。

再接下来的 $N-1$ 行，每行两个整数 $a_i, b_i$，表示 $a_i$ 和 $b_i$ 之间有一条边。

第 $2N$ 行一个整数 $M$，表示操作的次数。

再接下来的 $M$ 行，每行一个整数 $t_i$。

【输出格式】

一个整数，表示操作后整棵树的权值和的最大值。