Đường đi tổng lớn nhất

Cho một cây gồm \(n\) đỉnh, đỉnh \(i\) có viết số \(A_i\). Hãy tìm một đường đi đơn (dãy các đỉnh phân biệt liên tiếp nối bằng cạnh, không lặp đỉnh) trên cây sao cho tổng các số viết trên các đỉnh thuộc đường đi là lớn nhất. Đường đi có thể chỉ gồm đúng một đỉnh.

Input

• Dòng đầu tiên gồm số nguyên \(n\) (\(1 \le n \le 10^5\)).

• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(0 \le |A_i| \le 10^9\)).

• \(n - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u, v\) (\(1 \le u, v \le n\)) thể hiện có cạnh nối đỉnh \(u\) và đỉnh \(v\).

Dữ liệu vào luôn tạo thành một cây (liên thông, không có chu trình).

Output

In ra một số nguyên duy nhất là tổng lớn nhất có thể của một đường đi đơn trên cây.

Example

Input:

5
1 -2 3 4 -5
1 2
2 3
3 4
4 5

Output:

7

Note

Trong ví dụ trên, cây là một đường thẳng \(1 - 2 - 3 - 4 - 5\) với các giá trị \(1, -2, 3, 4, -5\). Đường đi đơn có tổng lớn nhất là đường đi chỉ gồm hai đỉnh \(3\) và \(4\), với tổng \(3 + 4 = 7\).