Mình muốn giúp Lâm Đồng trở thành địa phương có hệ thống giao thông nhộn nhịp nhất cả nước. Sau khi khảo sát, Mình biết rằng với mỗi thành phố ~i~, cần có ít nhất ~p_i~ chuyến taxi đi qua thành phố đó. Để làm được việc này, Mình sẽ đặt một số chuyến taxi, mỗi chuyến đi giữa hai thành phố được chọn trước.

Mạng lưới đường ở Lâm Đồng gồm ~N~ thành phố và ~N-1~ con đường hai chiều. Mỗi con đường nối trực tiếp hai thành phố, và từ mọi thành phố luôn có thể đi tới mọi thành phố khác. Nói cách khác, mạng lưới đường tạo thành một cây. Một chuyến taxi luôn đi theo đường đi ngắn nhất giữa hai thành phố đầu mút của nó; trên cây, đường đi này là duy nhất.

Một chuyến taxi được xem là đi qua tất cả các thành phố nằm trên đường đi của nó, bao gồm cả hai thành phố đầu mút. Với mỗi thành phố ~i~, Mình cần ít nhất ~p_i~ chuyến taxi đi qua thành phố đó. Mình muốn đặt ít chuyến taxi nhất có thể. Hãy tính số chuyến taxi tối thiểu cần đặt.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 100000)~: số thành phố.

• Dòng thứ hai chứa ~N~ số nguyên ~p_1,p_2,\dots,p_N~ ~(0 \le p_i \le 1000000000)~: số chuyến taxi tối thiểu cần đi qua từng thành phố.

• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1 \le u,v \le N)~, cho biết có một con đường nối trực tiếp hai thành phố ~u~ và ~v~.

• Dữ liệu đảm bảo các con đường tạo thành một cây.

Output

In ra một số nguyên duy nhất: số chuyến taxi ít nhất Mình cần đặt.

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

5