Given a tree of $n$ vertices. On vertex $i$, you can choose a number $a_i$ that $l_i \le a_i \le r_i$ and write on it.
The beauty of the tree is defined as the sum of $|a_u-a_v|$ for every edge $(u, v)$.
Find the maximum possible beauty of the tree.
### Input
- The first line contains an integer $n$.
- The next $n$ lines, each line contains 2 integers $l_i, r_i$.
- The next $n - 1$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$.
### Output
- Print the maximum beauty of the tree.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le l_i \le r_i \le 10^9$.
- $1 \le u, v \le n$.
### Example
Input:
```
3
1 3
4 6
7 9
1 2
2 3
```
Output:
```
8
```