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$.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 12 | $N \le 5\,000$, the tree is a chain and node 1 is an endpoint |
| 2 | 20 | $N \le 300\,000$, the tree is a chain and node 1 is an endpoint |
| 3 | 7 | $N \le 20$ |
| 4 | 22 | $N \le 5\,000$ |
| 5 | 39 | No additional constraints |
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