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