Mirko cảm thấy rất mệt mỏi với công việc khi đảm nhiệm vai trò là CEO trong một công ty phần mềm đa quốc gia có tiếng. Anh ấy quyết định sẽ chuyển tới Gorski Kotar và sống cuộc sống đơn giản hơn. Tuy nhiên, mùa đông ở chốn làng quê xa xôi nơi anh mới chuyển đến này đang rất khó khăn. Không một người hàng xóm nào của anh được sinh ra sau Thế Chiến thứ II, vì vậy anh quyết định sẽ tự thân đốn củi.

Hôm nay, anh ấy sẽ chặt thân cây đầu tiên của anh. Trước khi chặt, anh chia thân cây thành các phần vừa đủ lọt vào lò sưởi, đánh số và đo độ cứng của chúng.

Mirko là một lập trình viên, vì vậy anh ấy nhận ra rằng các phần trên thân cây và sự kết nối giữa chúng tạo thành một đồ thị cây.

Chi phí tổn thất của chiếc rìu anh dùng để cắt một đoạn liên kết hai phần trên cây bằng tổng độ cứng lớn nhất của hai thành phần liên thông được tạo thành sau khi anh cắt đoạn liên kết đó.

Mirko chỉ có duy nhất ~1~ chiếc rìu, vì vậy anh ấy muốn tổng chi phí tổn thất càng nhỏ càng tốt. Anh ấy muốn biết tổng chi phí tổn thất nhỏ nhất lên chiếc rìu, nếu anh ấy chặt toàn bộ thân cây thành các phần riêng lẻ mà anh đã chia từ trước.

Input

Dòng đầu tiên chứa một số nguyên ~n~, số lượng các phần trên cây. Các phần sẽ được đánh số từ ~1~ đến ~n~.

Dòng thứ hai chứa ~n~ số nguyên ~t_i~ ~(1 \le t_i \le 10^9)~ - độ cứng của phần thứ ~i~.

~n - 1~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~x~ và ~y~ ~(1 \le x, y \le n)~ - chỉ số các phần được nối trực tiếp.

Output

Xuất ra tổng chi phí tổn thất nhỏ nhất sau ~n - 1~ lần chặt.

Sample 1

Input

3
1 2 3
1 2
2 3

Output

8

Sample 2

Input

4
2 2 3 2
1 3
3 2
4 3

Output

15

Sample 3

Input

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

Output

26

Subtask

• ~5~ test đầu có ~1 \le n \le 10~.
• ~10~ test sau input đảm bảo phần thứ ~i~ và ~i + 1~ ~(1 \le i \le n - 1)~ được nối trực tiếp.
• ~5~ test sau có ~1 \le n \le 1000~.
• ~10~ test cuối cùng có ~1 \le n \le 10^5~.

Giải thích ví dụ 1:

Có ~2~ cách để chặt thân cây này. Anh ấy có thể cắt đoạn liên kết ~(1, 2)~ trước, tổn thất ~1 + 3 = 4~, sau đó cắt đoạn liên kết ~(2, 3)~, tổn thất ~2 + 3 = 5~. Tổng chi phí tổn thất trong trường hợp này là ~9~.

Một cách khác, anh ấy có thể cắt đoạn ~(2, 3)~ trước, sau đó cắt đoạn ~(1, 2)~. Tổng chi phí tổn thất trong trường hợp này sẽ là ~(2 + 3) + (1 + 2) = 8~.