Đất nước Alpha có \(n\) thành phố, đánh số từ 1 đến \(n\). Các thành phố được nối với nhau bởi \(n-1\) đường hai chiều, mỗi đường nối một cặp thành phố và bảo đảm có đường đi lại giữa hai thành phố bất kì trong nước (trực tiếp hoặc đi qua một số thành phố khác).

Alice đang lên kế hoạch thăm một số thành phố của đất nước Alpha. Alice đã đánh giá \(s_i(1<=i<=n)\) là mức độ yêu thích thăm thành phố \(i\). Hành trình thăm đất nước Alpha của Alice là một dãy các thành phố, hai thành phố liên tiếp trên hành trình có đường đi trực tiếp, không có thành phố nào được thăm lại.

Yêu cầu: Alice muốn tìm hành trình mà tổng mức độ yêu thích của các thành phố trên hành trình tìm được là lớn nhất (hành trình có thể chỉ thăm một thanh phố).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(n\);

• Dòng thứ hai gầm \(n\) số nguyên \(s_1, s_2, ... , s_n(|s_i|<=10^6;1<=i<=n);\)

• Dòng thứ \(k (1<=k<=n-1)\) trong \(n-1\) dòng tiếp theo chứa hai số nguyên \(i_k,j_k\) mô tả đường đi thứ \(k\).

Kết quả

• Gồm một dòng chứa một số là tổng mức độ yêu thích của hành trình tìm được.

Ràng buộc

• Có 30% số test ứng với 30% số điểm của bài có \(n<=100\) và các giá trị si đều bằng 1;

• Có 20% số test ứng khác với 20% số điểm của bài có \(n<=10^5\) và các giá trị si đều bằng 1;

• Có 50% số test còn lại ứng với 50% số điểm của bài có \(n<=10^5.\)

Sample Input

5
-1 2 3 4 -5
1 2
1 3
1 4
4 5

Sample Output

6