Problem Description

Borova Suma, located across the river, was illuminated by the May sun just an hour ago, but now it has become hazy, blurred, and dispersed. Only one magical tree remains, a tree with $N$ nodes...

Ivan observed this tree from room 119, firmly rooted at node labeled with number $1$. He then observed the tree more closely and found that each node had a number $a$. Suddenly, he thought of the definition of a $k$-good subtree. 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) \bmod k$ holds, and for each node $v$ within the subtree, $a_v < k$ is satisfied. For each number $k$, there exists a natural instability of $k$-good subtrees, denoted as $f(k)$.

When he came to his senses again, he found himself standing in front of the tree, with a magical axe in his right hand. Ivan decided to cut some branches and, for each subtree obtained after removing certain edges, choose a number $k$ such that the subtree is $k$-good. The decision on which edges to cut and the $k$ values chosen for each resulting subtree, Ivan called "cutting". We define the instability of cutting as the sum of $f(k_i)$ for all resulting $k$-good subtrees. Please help Ivan determine the minimum possible instability of cutting.

Input Format

The first line is a natural number $N$, representing the number of nodes in the tree.

The second line contains $N$ numbers, where the $i$-th number represents the weight $a$ of node $i$ ($0 \leq a \leq N - 1$).

The third line contains $N$ numbers, where the $k$-th number represents the value of function $f(k)$ ($1 \leq f(k) \leq 10^9$).

The next $N-1$ lines describe the structure of the tree, with each line containing two numbers $u$ and $v$ ($1 \leq u, v \leq N, u \neq v$), indicating an edge between node $u$ and node $v$.

Output Format

Output the minimum possible "cutting instability" on a single line.

Sample Input and Output

Input Sample #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 Sample #1

11

Input Sample #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 Sample #2

4

Notes/Hints

[Sample Explanation]

The left image is for Sample 1, and the right image is for Sample 2.

[Data Range]

In all subtasks, the condition $1 \leq N \leq 3 \times 10^5$ is satisfied.

• Subtask 1 (12 points): $N \leq 5000$, the tree is a chain, and node $1$ is an endpoint of the chain.
• Subtask 2 (20 points): $N \leq 300000$, the tree is a chain, and node $1$ is an endpoint of the chain.
• Subtask 3 (7 points): $N \leq 20$;
• Subtask 4 (22 points): $N \leq 5000$;
• Subtask 5 (39 points): No additional restrictions.

见题面 Input 部分

见题面 Output 部分