The inventor SHTSC, who once invented a parts assembly machine, has unveiled his new invention: a fusion reactor—a mysterious device capable of producing a large amount of clean energy.

As is well known, there are two difficulties in utilizing energy generated by nuclear fusion: first, controlling the intensity of the fusion reaction, and second, using as little energy as possible to trigger the fusion reaction. SHTSC has already perfectly solved the first problem. A fusion reactor consists of several connected fusion blocks. To ensure the fusion reaction is controllable, SHTSC guarantees that any two fusion blocks can be reached from each other through the links between them, and no fusion block can return to itself without repeating a link.

However, SHTSC has not yet fully solved the second problem. In the fusion reactor he designed, each fusion block requires a certain initial energy $d_i$ to be triggered. However, SHTSC does not need to manually trigger all fusion blocks. This is because once a fusion block is triggered, it will transmit $c_i$ units of energy to all directly connected fusion blocks that have not yet been triggered. In this way, subsequently triggered fusion blocks can be activated with lower initial energy, or may even be able to trigger themselves without additional external energy, thereby reducing the total energy consumption.

Given a fusion reactor, find the minimum energy required to trigger all fusion blocks.

Input

The first line contains an integer $n$, representing the total number of fusion blocks, numbered from $1$ to $n$.

The second line contains $n$ integers, representing $d_i$.

The third line contains $n$ integers, representing $c_i$.

The following $n-1$ lines each contain two integers $u$ and $v$, representing that the fusion blocks numbered $u$ and $v$ are connected.

The input is guaranteed to satisfy the problem description.

Output

A single integer representing the minimum amount of energy required to trigger all fusion blocks.

Examples

Input 1

5
1 1 1 1 1
1 1 1 1 1
1 2
2 3
3 4
4 5

Output 1

1

Input 2

4
1 2 3 4
1 1 1 1
1 2
1 3
1 4

Output 2

7

Input 3

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

Output 3

17

Note

Example 1: Only one arbitrary fusion block needs to be triggered to activate the entire fusion reactor.

Example 2: Manually trigger fusion block 1; the remaining fusion blocks will then require 1, 2, and 3 units of energy respectively to be activated.

Example 3: Manually triggering fusion blocks 6, 4, and 5 consumes 6 units of energy. Activating blocks 3 and 2 consumes an additional 6 and 3 units of energy, and finally, activating block 1 consumes 2 units, for a total consumption of 17 units of energy.

Subtasks

This problem has two types of test data, each accounting for 50%.

Type A: $c_i \le 1$ For 30% of the data: $c_i = 1$. For 60% of the data: $n \le 200$. * For 100% of the data: $n \le 100000$.

Type B: $c_i \le 5$ For 20% of the data: $n \le 20$. For 60% of the data: $n \le 200$. * For 100% of the data: $n \le 2000$.

For all data, $1 \le d_i$, $\sum d_i \le 10^9$. The input is guaranteed to satisfy the problem description.