The pine forest on the opposite bank of the river, illuminated by the May sun just an hour ago, has become blurred, smeared, and dissipated. Only one giant tree remained, a tree with $N$ nodes...

Ivan, from room no. 119, observed this tree, firmly rooted at the node labeled with the number 1. After observing the tree more closely, he noticed that there is a number $a_i$ in each node. Suddenly, the definition of a $k$-good subtree dawned on him. A subtree is $k$-good if for every edge connecting nodes $(u, v)$ where $u$ is the parent of $v$, the condition $a_v = (a_u + 1) \pmod k$ holds, and additionally, for every node $v$ within the subtree, $a_v < k$ holds. For every number $k$, there exists a natural instability of $k$-good trees, denoted as $f(k)$.

When he looked again, he noticed he was floating in front of the tree with a magic saw in his right hand. Ivan decided to cut some branches, and for each subtree obtained by removing the sawn edges, choose a number $k_i$ such that it is $k_i$-good. A pair consisting of a set of edges to be cut and the numbers $k_i$ for each resulting subtree such that the corresponding subtree is $k_i$-good, Ivan decided to call a cutting. The instability of a cutting is defined as the sum of $f(k_i)$ over all resulting subtrees. Help Ivan determine the minimum possible instability of a cutting!

Input

The first line contains a natural number $N$, the number of nodes in the tree. The second line contains $N$ numbers where the $i$-th number denotes $a_i$ ($0 \le a_i \le N - 1$). The third line contains $N$ numbers where the $k$-th number denotes $f(k)$ ($1 \le f(k) \le 10^9$). The next $N - 1$ lines contain the description of the tree; the $i$-th line contains the numbers $u_i$ and $v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$) which indicate that there is an edge between nodes $u_i$ and $v_i$.

Output

In the only line, print the minimum possible instability of a cutting.

Subtasks

In all subtasks, $1 \le N \le 300\,000$.

Examples

Input 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

Output 1

11

Input 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

Output 2

4

Note

(a) Sketch of the cutting for the first example (b) Sketch of the cutting for the second example