There is an apple tree growing in Hakurei shrine consisting of $n$ vertices and rooted at $1$, the $i^{th}$ vertex has an apple that value $A_i$. Each subtree rooted at $i$ also has a limit $B_i$, no more than $B_i$ apples in subtree $i$ can be picked. Determine the maximum apple value Marisa can have.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
- The third line contains $n$ integers $B_i$.
- The next $n-1$ lines, each line contains two integers $u, v$, there is an edge between $u$ and $v$.
### Output
- Print the maximum value.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le A_i \le 10^9$.
- $0 \le B_i \le n$.
- $1 \le u, v \le n$.
### Example
Input:
```
4
1 4 2 3
2 1 1 0
1 2
2 3
2 4
```
Output:
```
5
```
