Cây đẹp

Cho một cây gồm \(n\) đỉnh. Với mỗi đỉnh \(i\), bạn được viết một số nguyên \(a_i\) lên đỉnh đó, miễn sao \(l_i \le a_i \le r_i\).

Độ đẹp của cây được tính bằng tổng \(|a_u - a_v|\) lấy trên mọi cạnh \((u, v)\) của cây.

Hãy chọn các số \(a_i\) sao cho độ đẹp của cây là lớn nhất có thể, và cho biết giá trị lớn nhất đó.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).

• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i, r_i\) (\(1 \le l_i \le r_i \le 10^9\)).

• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\)) thể hiện có cạnh nối giữa đỉnh \(u\) và đỉnh \(v\).

Dữ liệu vào đảm bảo các cạnh tạo thành một cây.

Output

In ra một số nguyên duy nhất là độ đẹp lớn nhất có thể của cây.

Example

Input:

3
1 3
4 6
7 9
1 2
2 3

Output:

8

Note

Trong ví dụ trên, ta chọn \(a_1 = 1\), \(a_2 = 4\), \(a_3 = 9\) (hoặc một cách chọn khác cho cùng giá trị). Khi đó \(|a_1 - a_2| + |a_2 - a_3| = 3 + 5 = 8\), đây là giá trị lớn nhất có thể đạt được.