Ánh nắng ban mai rực rỡ len lỏi qua từng tán lá rậm rạp của khu rừng Viridian Forest, đánh thức muôn loài sinh vật kỳ bí đang say giấc nồng, đồng thời cũng chính thức mở ra chương đầu tiên trong chuyến hành trình vĩ đại của Ash và người bạn đồng hành thân thiết Pikachu. Khu rừng này từ lâu đã được giới đạo tặc Team Rocket và các nhà thám hiểm truyền tai nhau về một cấu trúc địa lý vô cùng kỳ lạ và phức tạp, không giống với bất kỳ hệ sinh thái nào trên thế giới. Theo những ghi chép cổ xưa mà Professor Oak đã dày công nghiên cứu và trao lại cho Ash, khu rừng không phải là một mặt phẳng thông thường mà được chia thành \(n\) bãi cỏ biệt lập. Những bãi cỏ này được kết nối với nhau bởi chính xác \(n-1\) con đường mòn phủ đầy rêu xanh và lá khô, tạo thành một hệ thống mạng lưới hoàn hảo sao cho từ một bãi cỏ bất kỳ, người ta luôn có thể tìm được đường đi đến mọi bãi cỏ khác mà không bị chia cắt, một cấu trúc mà các nhà toán học gọi là "cây".

Tại mỗi bãi cỏ thứ \(i\), hệ thống radar trên chiếc máy Pokedex thế hệ mới của Ash liên tục phát ra tiếng bíp bíp, quét được sự hiện diện của một chú Pokemon hoang dã mang trong mình mức năng lượng chiến đấu tiềm tàng là \(a_i\). Với ngọn lửa nhiệt huyết rực cháy trong tim và khát khao thu thập những người bạn đồng hành mạnh mẽ nhất, Ash quyết tâm thu phục một đội hình Pokemon từ khu rừng này sao cho tổng mức năng lượng chiến đấu của toàn đội đạt đến ngưỡng vĩ đại nhất có thể. Tuy nhiên, mẹ thiên nhiên luôn có những quy luật khắc nghiệt của riêng mình: các loài Pokemon sống ở hai bãi cỏ kề nhau (tức là có một con đường mòn nối trực tiếp giữa chúng) thường có tập tính bảo vệ lãnh thổ cực kỳ cao và coi nhau như những kẻ thù không đội trời chung. Nếu Ash vô tình thu phục cả hai Pokemon ở hai bãi cỏ kề nhau này, chúng sẽ mang theo sự thù hằn vào bên trong những quả Pokeball, lập tức lao vào cắn xé và đánh nhau loạn xạ, gây ra sự hỗn loạn tột độ và có nguy cơ phá hủy hoàn toàn đội hình mà cậu đang cất công xây dựng.

Nhận thức được mối nguy hiểm tiềm tàng này, Ash tự đặt ra một quy tắc sinh tử: tuyệt đối không bao giờ được phép thu phục hai Pokemon ở hai bãi cỏ có đường nối trực tiếp với nhau. Đứng trước một hệ sinh thái đan xen phức tạp cùng hàng vạn ngã rẽ của tự nhiên, Ash đang thực sự đau đầu trong việc lựa chọn mục tiêu. Bằng tất cả kiến thức về quy hoạch động trên cây mà bạn đã rèn luyện, hãy giúp Ash tính toán một chiến thuật hoàn hảo xem tổng mức năng lượng chiến đấu lớn nhất mà cậu có thể thu phục được một cách an toàn tuyệt đối là bao nhiêu, để cậu có thể tự tin bước tiếp trên con đường trở thành Pokemon Master.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^5\)) — số lượng bãi cỏ trong Viridian Forest.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) — mức năng lượng chiến đấu của Pokemon tại bãi cỏ thứ \(i\).
• \(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\)) mô tả một con đường mòn nối trực tiếp giữa bãi cỏ \(u\) và bãi cỏ \(v\).

Output

• In ra một số nguyên duy nhất là tổng mức năng lượng lớn nhất có thể thu phục mà không vi phạm quy tắc lãnh thổ.

Example

3
10 20 30
1 2
2 3

40

5
50 10 10 10 10
1 2
1 3
1 4
1 5

50

7
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7

23

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(1 \le n \le 20\).
• Subtask \(2\) (\(30\%\) điểm): \(1 \le n \le 2000\).
• Subtask \(3\) (\(50\%\) điểm): Không còn ràng buộc gì thêm.