Instability

A pine forest on the far bank of the river, lit by the May sun only an hour ago, has blurred, smeared, and dissolved. Only one giant tree is left, a tree with $N$ nodes, firmly rooted at node $1$.

Ivan, in room 119, was watching the tree. On a closer look, he noticed that each node $i$ holds a number $a_i$. Then the definition of a $k$-good subtree came to him. A subtree is $k$-good if, for every edge $(u, v)$ where $u$ is the parent of $v$, $a_v = (a_u + 1) \bmod k$ holds, and every node $v$ in the subtree satisfies $a_v < k$. For each natural number $k$, the instability of $k$-good trees is given as $f(k)$.

When he looked back at the tree, Ivan was floating in front of it with a magic saw in his right hand. Ivan decided to cut some branches. Removing the cut edges splits the tree into several subtrees. For each resulting subtree, Ivan picks a number $k_i$ so that the subtree is $k_i$-good. The pair of a chosen set of edges to cut and the numbers $k_i$ for each resulting subtree is called a cut. The instability of a cut is the sum of $f(k_i)$ over all resulting subtrees. Help Ivan find the minimum possible instability of a cut!

The first line contains the natural number $N$, the number of nodes in the tree.

The second line contains $N$ integers, where the $i$-th integer is $a_i$ ($0 \le a_i \le N-1$).

The third line contains $N$ integers, where the $k$-th integer is $f(k)$ ($1 \le f(k) \le 10^9$).

Each of the next $N-1$ lines contains two integers $u_i$ and $v_i$, meaning there is an edge between nodes $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$).

Print the minimum possible instability of a cut on a single line.