Bữa tiệc

Công ty XYZ có \(N\) người được tổ chức theo sơ đồ hình cây: \(K\) là cha của \(L\) có nghĩa là \(K\) là cấp trên trực tiếp của \(L\), ông Giám đốc là gốc. Nhân viên thứ \(i\) có độ vui vẻ \(h_i\).

Ông Giám đốc muốn tổ chức một bữa tiệc có tổng độ vui vẻ 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: Em hãy giúp ông Giám đốc tìm độ vui vẻ lớn nhất có thể.

Input

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương \(N\) (\(1 < N < 2025\)).

• Dòng thứ hai ghi \(N\) số \(h_1, h_2, \ldots, h_N\) (\(-128 < h_i < 127\)).

• \(N-1\) dòng cuối cùng, mỗi dòng ghi \(2\) số \(L\) và \(K\), nghĩa là \(K\) là cấp trên trực tiếp của \(L\).
  Ông Giám đốc là người duy nhất không có cấp trên trực tiếp. Các số trên cùng một dòng cách nhau một dấu cách.

Output

In ra một số nguyên là tổng độ vui vẻ lớn nhất tìm được.

Example

Input:

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

Output:

5

Note

Cây có gốc là người \(1\) (Giám đốc), người \(1\) có hai nhân viên trực tiếp là \(2\) và \(3\); người \(2\) có hai nhân viên \(4\), \(6\); người \(3\) có hai nhân viên \(5\), \(7\). Chọn Giám đốc \(1\) cùng bốn người \(4, 5, 6, 7\): không ai có cấp trên trực tiếp cũng dự tiệc, tổng độ vui vẻ là \(5\). Không có cách nào lớn hơn.