河对岸的松树林，在一小时前还沐浴在五月的阳光下，现在已经变得模糊、混杂并消散了。只剩下一棵巨大的树，一棵拥有 $N$ 个节点的树……

Ivan 在 119 号房间里观察着这棵树，它牢牢地以编号为 $1$ 的节点为根。在更仔细地观察这棵树后，他注意到每个节点上都有一个数字 $a_i$。突然，他的脑海中浮现出了 $k$-好连通子树的定义。

一个连通子树是 $k$-好的，如果满足以下条件：

• 对于该连通子树中连接节点 $(u, v)$ 的每条边（其中 $u$ 是 $v$ 在原树中的父节点），均满足 $a_v = (a_u + 1) \bmod k$；
• 此外，对于该连通子树内的每个节点 $v$，均满足 $a_v < k$。

对于每个正整数 $k$，都存在一个 $k$-好树的自然不稳定性，记为 $f(k)$。

当他再次回过神来时，他发现自己正漂浮在树前，右手拿着一把魔锯。Ivan 决定切断一些边，并对于通过移除被切断的边所得到的每个连通子树，选择一个数字 $k_i$ 使得该连通子树是 $k_i$-好的。选择要切断的边集以及为每个得到的连通子树选择满足其为 $k_i$-好的数字 $k_i$ 的方案，Ivan 称之为一次割。一次割的不稳定性定义为所有得到的连通子树的 $f(k_i)$ 之和。请帮助 Ivan 确定一次割的最小可能不稳定性！

输入格式

第一行包含一个正整数 $N$，表示树的节点数。

第二行包含 $N$ 个整数，其中第 $i$ 个整数表示 $a_i$ ($0 \le a_i \le N - 1$)。

第三行包含 $N$ 个整数，其中第 $k$ 个整数表示 $f(k)$ ($1 \le f(k) \le 10^9$)。

接下来的 $N - 1$ 行描述这棵树，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le N, u_i \ne v_i$)，表示节点 $u_i$ 和 $v_i$ 之间存在一条边。

输出格式

输出唯一的一行，包含一次割的最小可能不稳定性。

子任务

对于所有子任务，均满足 $1 \le N \le 300\,000$。

样例

输入样例 1

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

输出样例 1

11

输入样例 2

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

输出样例 2

4

样例说明

(a) 第一组样例的割示意图 (b) 第二组样例的割示意图