Phương Nam có ~N~ khu vực hành chính, được đánh số từ ~1~ đến ~N~, được kết nối liên thông bởi ~N − 1~ con đường tạo thành dạng cây trong lý thuyết đồ thị. Mỗi khu vực tương ứng với một đỉnh của cây, mỗi con đường tương ứng với một cạnh của cây. Nhắc lại, cây là một đồ thị vô hướng, liên thông và không có chu trình. Mỗi khu vực người ta gán cho một giá trị biểu thị mức độ phát triển khu vực đó, khu vực thứ i có có giá trị ~A_i~.

Nhằm quy hoạch phát triển các khu vực một cách hiệu quả, người ta đánh giá một cụm ~S~ các khu vực liên thông nhau thông qua các con đường nối giữa chúng trong cụm đó bởi một độ hiệu quả. Giá trị độ hiệu quả này được tính bằng hiệu của giá trị lớn nhất trong số các giá trị khu vực thuộc ~S~ và giá trị nhỏ nhất trong số các giá trị khu vực thuộc ~S~. Nói cách khác, với một cụm liên thông ~S~, giá trị của ~S~ là ~max_{u \in S} A_u − min_{u \in S} A_u~.

Người ta muốn chia toàn bộ ~N~ khu vực thành các cụm khu vực riêng biệt, mỗi cụm bao gồm một hoặc nhiều khu vực liên thông nhau bởi các con đường nối các khu vực trong cụm đó và đánh giá độ hiệu quả trên mỗi cụm. Tổng độ hiệu quả của một cách chia như vậy được tính bằng tổng giá trị của các cụm liên thông trong cách chia đó.

Yêu cầu: Hãy tìm cách chia toàn bộ ~N~ khu vực thành các cụm có tổng độ hiệu quả lớn nhất.

Dữ liệu

Vào từ file văn bản SOUTH.INP:

• Dòng thứ nhất chứa một số nguyên ~N~ ~(1 \le N \le 3 \times 10^5)~ là số lượng khu vực ở Phương Nam.

• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, . . . , A_N~ ~(1 \le Ai \le 10^9)~ mô tả độ phát triển của khu vực tương ứng.
• Dòng thứ ~i~ trong ~N − 1~ dòng tiếp theo chứa hai số nguyên ~u_i~, ~v_i~ ~(1 \le u_i, v_i \le N)~ mô tả mộtcon đường nối hai khu vực ~u_i~ và ~v_i~. Dữ liệu đảm bảo các con đường này tạo thành một cây.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản SOUTH.OUT:

• Một số nguyên duy nhất là tổng độ hiệu quả lớn nhất tìm được.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 20~.
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 2000~, và tất cả các đỉnh có bậc không quá ~2~.
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: Tất cả các đỉnh có bậc không quá ~2~.
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài: Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu ~1~

4
3 8 9 1
1 2
2 3
3 4

Kết quả ~1~

13

Dữ liệu ~2~

9
2 6 3 8 5 1
1 5 4
1 2
1 3
5 1
4 3
3 7
5 9
8 3
6 5

Kết quả ~2~

15