Bạn được cho một cái cây gồm \(n\) đỉnh và đúng \(n - 1\) cạnh, các đỉnh được đánh số từ \(1\) tới \(n\). Trên mỗi đỉnh \(i\) ban đầu chứa một số nguyên \(v_i\).

Mỗi thao tác, bạn được phép:

• Chọn một cây con bất kì miễn là cây con đó chứa đỉnh \(1\).
• Tăng hoặc giảm toàn bộ giá trị trên tất cả các đỉnh của cây con đúng \(1\) đơn vị.

Một cây được gọi là cây O nếu như tất cả các đỉnh có trong cây đều có giá trị là \(0\).

Tính số thao tác ít nhất cần thực hiện để biến cái cây bạn được cho thành cây O.

Đầu vào

Dòng đầu tiên chứa số nguyên dương \(n\) là số lượng đỉnh của cây. \((1 \le n \le 10^5)\)

\(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) thể hiện đỉnh \(a\) được nối với đỉnh \(b\). \((1 \le a, b \le n, a ≠ b)\)

Dòng cuối cùng chứa \(n\) số nguyên \(v_1, v_2, ..., v_n\) là giá trị ban đầu của các đỉnh trên cây. \((|v_i| \le 10^9)\)

Đầu ra

Một số nguyên duy nhất là số thao tác ít nhất cần thực hiện để biến cây của bạn về cây O.

Giới hạn

\(10\%\) số test: \(n \le 10\)

\(20\%\) số test: \(n \le 1000, |v_i| \le 10^4\)

\(30\%\) số test: \(|v_i| \le 10^4\)

\(40\%\) số test: Không có ràng buộc gì thêm

Ví dụ

Đầu vào

3
1 2
1 3
3 -2 1

Đầu ra

7

Giải thích