Nam vừa mua được một cây rìu nên hôm nay anh ấy quyết định thử nó trên cây táo của mẹ mình. Cây táo gồm có ~n~ trái táo được đánh số từ ~1 \to n~. Những trái táo liên kết với nhau qua các cành tạo thành đồ thị dạng cây.

Khi cắt một cành nối giữa hai trái táo sẽ tạo thành hai đùm táo và mỗi đùm có một quả táo với khối lượng lớn nhất, Nam sẽ tốn khoảng thời gian bằng tổng khối lượng hai quả táo đó.

Yêu cầu: Tìm thời gian ngắn nhất để cắt hết ~n-1~ cành.

Input

• Dòng đầu gồm một số nguyên ~n~ là số trái táo.
• Dòng thứ hai gồm ~n~ số nguyên ~m_i~ là khối lượng của quả táo thứ ~i~ (~1 \le m_i \le 10^9~).
• Mỗi dòng trong ~n-1~ dòng còn lại gồm hai số nguyên ~x~ và ~y~ cho biết có cành nối trực tiếp giữa hai quả táo ~x~ và ~y~ (~1 \le x, y \le n~).

Output

• In ra thời gian ngắn nhất để cắt hết ~n-1~ cành.