Cây 0

Cho một cây gồm \(n\) đỉnh được đánh số từ \(1\) đến \(n\). Mỗi đỉnh \(i\) của cây mang một giá trị nguyên \(A_i\).

Một tập con các đỉnh của cây được gọi là độc lập nếu không có hai đỉnh nào trong tập con đó được nối trực tiếp với nhau bởi một cạnh. Giá trị của một tập đỉnh bằng tổng các giá trị \(A_i\) của các đỉnh thuộc tập đó. Tập rỗng có giá trị bằng \(0\).

Hãy tìm giá trị lớn nhất của một tập đỉnh độc lập trên cây.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).

• Dòng thứ hai chứa \(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 chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\)) thể hiện có cạnh nối giữa đỉnh \(u\) và đỉnh \(v\).

Dữ liệu vào luôn tạo thành một cây hợp lệ.

Output

In ra một số nguyên duy nhất là số thao tác ít nhất cần thực hiện.

Example

Input:

3
1 -1 1
1 2
1 3

Output:

3

Note

Với ví dụ trên, đỉnh \(1\) có giá trị \(1\), đỉnh \(2\) có giá trị \(-1\), đỉnh \(3\) có giá trị \(1\).

Lời giải dựa trên nhận xét: coi đỉnh \(1\) có một "cha ảo" với giá trị luôn bằng \(0\). Khi đó, với mỗi đỉnh \(i\) (kể cả đỉnh \(1\)), số thao tác cần dùng để triệt tiêu chênh lệch giữa \(i\) và cha của nó (trong cây gốc tại đỉnh \(1\)) đúng bằng \(|A_i - A_{parent(i)}|\), và tổng các giá trị này trên toàn bộ các đỉnh chính là đáp số — đây cũng là chặn dưới không thể cải thiện được.

Với ví dụ trên: \(|A_1 - 0| + |A_2 - A_1| + |A_3 - A_1| = |1 - 0| + |{-1} - 1| + |1 - 1| = 1 + 2 + 0 = 3\).