Dì ghẻ thường hay bày trò bắt nạt Tấm, vấn đề lần này liên quan đến tin học.

Máy tính hiện lên một cây nhị phân có ~n~ nút (mỗi nút có nhiều nhất 2 con). Tại mỗi nút ~i~ có ghi một số nguyên ~a_i~. Mỗi thao tác Tấm được chọn một nút và lấy số ghi trong nút đó tăng lên hoặc giảm đi 1 đơn vị. Yêu cầu của dì ghẻ là Tấm phải chuyển cây về trạng thái thỏa mãn:

• Số ghi trong mỗi nút lá bằng 0 hoặc 1,
• Số ghi trong một nút nhánh bằng tổng các số ghi trong các nút con.

Yêu cầu: Hãy giúp cô Tấm tìm số thao tác ít nhất để thực hiện yêu cầu nêu trên.

Input

• Dòng đầu chứa số ~n (1 \le n \le 5000)~,
• Dòng thứ 2 chứa ~n~ số ~a_1, a_2, ..., a_n (\forall{i}: 0 \le a_i \le 5000)~
• ~n-1~ dòng tiếp theo, mỗi dòng ghi 2 số ~x, y~ cho biết hai nút ~x, y~ có quan hệ cha-con. Nút 1 luôn luôn là gốc của cây.

Các số trên 1 dòng cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số thao tác ít nhất tìm được.

Sample

Input #1

5
5 1 3 0 1
1 2
1 3
3 4
3 5

Output #1

4

Problem source: PreVNOI Ⅶ (NINH BÌNH 2017)