Bạn vừa được HCV IOI nên thầy Tùng quyết định thưởng cho bạn. Thầy cho bạn một cây có $n$ đỉnh. Với mỗi đỉnh $i$ cho 2 số $l_i\le r_i$. Việc bạn cần làm là chọn một số $v_i$ ở mỗi đỉnh sao cho $l_i\le v_i\le r_i$ và số tiền được thưởng (tính bằng triệu VND) sẽ là tổng của $|v_i-v_j|$ với toàn bộ các cạnh $(i,j)$ vô hướng của cây. Hãy in ra số tiền nhiều nhất bạn có thể được thầy thưởng.

Input

• Dòng đầu tiên là số nguyên dương $n\le {10}^5$ là số đỉnh của cây.
• $n$ dòng tiếp theo mỗi dòng $i$ gồm 2 số $l_i\le r_i\le {10}^9$ là chỉ số của đỉnh thứ $i$.
• $n-1$ dòng tiếp theo mỗi dòng là 2 số $u,v$ là cạnh của cây.

Output

• In ra một số là số tiền lớn nhất bạn có thể được thưởng.

Subtasks

• Subtask 1: $n\le 20$.
• Subtask 2: Với mỗi $i<n$, tồn tại một cạnh $i$ với $i+1$.
• Subtask 3: Không có điều kiện gì thêm.

Sample Test

Input:

3
1 3
4 6
7 9
1 2
2 3

Output:

8