Trên một hòn đảo xinh đẹp có chứa nhiều kho báu, mỗi kho báu được đánh số thứ tự từ 1 đến ~n~. Trong mỗi kho báu có chứa số lượng vàng nhất định với đơn vị kilogram. Sơ đồ các kho báu giống hình ảnh cây trong đồ thị. Tức là giữa 2 kho báu bất kì luôn có đường đi giữa chúng và trên hòn đảo có tất cả ~n-1~ con đường nối các kho báu. Hùng được giao nhiệm vụ bảo vệ các kho báu. Anh nghĩ ra một cách để bảo vệ tất cả kho báu là sẽ phá hủy các con đường để kẻ trộm không thể đi mọi kho báu. Khi một con đường bị phá hủy sẽ chia các kho báu thành 2 phần không liên thông. Sức lực của Hùng bỏ ra được tính bằng tổng số vàng của kho vàng lớn nhất trong thành phần thứ nhất và kho vàng lớn nhất trong thành phần thứ 2. Hùng muốn phá hủy được mọi con đường nhưng lại mất ít sức lực nhất có thể.

Yêu cầu: Hãy tìm thứ tự phá hủy các con đường để tổng sức lực bỏ ra là ít nhất.

Input

• Dòng đầu chứa số nguyên ~n~ là số kho báu.
• Dòng thứ 2 chứa ~n~ số nguyên ~t_i~ (~1 \le t_i \le 10^9~), trong đó ~t_i~ là số kilogram vàng của kho báu 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~) thể hiện cạnh nối giữa kho báu ~x~ và kho báu ~y~.

Output

• In ra tổng sức lực tối thiểu mà H cần dùng để phá hủy ~n-1~ con đường.