Để trang trí căn phòng của mình, 3T quyết định mua về một bức tranh thật đẹp, do là người yêu thiên nhiên nên bức trang 3T chọn có dạng đồ thị cây có \(N\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(N\). Để dán bức tranh lên tường, 3T cần cho keo dán vào các đỉnh của cây, mỗi đỉnh \(i\) mất chi phí \(a_i\). Để đảm bảo bức tranh hình cây được dán chắc chắn thì mỗi cạnh của cây đều phải được dán ít nhất tại một đầu. Hãy giúp 3T tính chi phí tối thiểu để dán được bức tranh của mình lên tường nhé!

Dữ liệu vào

• Dòng đầu tiên là số \(N\) là số đỉnh của đồ thị.
• Dòng tiếp theo ghi \(N\) số nguyên dương \(a_1, a_2, a_3... a_N\) là các số được gán với N đỉnh theo thứ tự.
• \(N-1\) dòng tiếp theo, mỗi dòng có 2 số \(u\) và \(v\) là cạnh nối đỉnh \(u\) đến \(v\).

Dữ liệu ra

• Một số duy nhất là đường đi có tổng lớn nhất.

Ràng buộc

• \(N \le 2 \times 10^5\)
• \(a_i \le 10^9\)

Input 1

4
4 2 2 1
1 3
2 3
2 4

Output 1

3