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\ne 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\mathrm{\%}$ số test: $n\le 10$

$20\mathrm{\%}$ số test: $n\le 1000,|v_i|\le {10}^4$

$30\mathrm{\%}$ số test: $|v_i|\le {10}^4$

$40\mathrm{\%}$ 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