Một công ty có ~N~ nhân viên (kể cả giám đốc), công ty được tổ chức theo sơ đồ hình cây: Khi ~K~ là cha của ~L~, điều đó có nghĩa là ~K~ là cấp trên trực tiếp của ~L~, như vậy, ông giám đốc là gốc cây. Nhân viên thứ ~i~ (có tên là ~i~) có độ vui vẻ ~h_i~. Chú ý rằng giám đốc không nhất thiết phải có tên là ~1~.

Ông giám đốc muốn tổ chức một bữa tiệc có tổng độ vui vẻ của những người đến dự là lớn nhất và nếu có một nhân viên nào đó đi dự thì sẽ không có cấp trên trực tiếp của anh ta. Đương nhiên là ông giám đốc phải có mặt.

Yêu cầu: Bạn hãy giúp ông giám đốc tổ chức bữa tiệc sao cho độ vui vẻ là lớn nhất có thể.

Input

Vào từ file BUATIEC.INP:

• Dòng đầu chứa số nguyên dương ~N\ (1\le N \le 2000)~;
• Dòng tiếp theo chứa ~N~ số nguyên ~h_i\ (-128 \le h_i \le 127)~;
• ~N-1~ dòng cuối cùng chứa lần lượt hai số nguyên dương ~L~ và ~K~ ~(1 \le L, K\le N;\ L \neq K)~.

Output

Ghi ra tệp BUATIEC.OUT:

• Một số nguyên là tổng độ vui vẻ lớn nhất có thể nhận được.

Subtasks

• Subtask 1: ~50\%~ test có ~n \le 1000~;
• Subtask 2: ~50\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

7
1 1 1 1 1 1 1
2 1
3 1
4 2
6 2
5 3
7 3

Sample Output 1

5

Giải thích:

Chọn nhân viên tên ~4,5,6,7~ và ông giám đốc tên ~1~.