Cho một cây nhị phân gồm \(n\) nút, các nút được đánh số từ \(1\) đến \(n\), trong đó nút \(1\) là nút gốc. Mỗi nút được gán một số nguyên \(a_i\). Xét thao tác tăng hoặc giảm số gán trên một nút, mỗi thao tác mất chi phí bằng \(1\).

Một cây được gọi là dạng chuẩn nếu các nút lá được gán số \(0\) hoặc \(1\), các nút khác được gán giá trị bằng tổng giá trị được gán cho các nút con của nút đó.

Yêu cầu: Tìm cách đưa cây về dạng chuẩn với chi phí nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^5\)).
• Tiếp theo là \(n-1\) dòng, mỗi dòng chứa hai số nguyên \(x, y\) mô tả một cạnh của cây.

Output

• Gồm một dòng chứa một số nguyên là chi phí nhỏ nhất để đưa cây về dạng chuẩn.

Example

3
3 3 3
1 2
1 3

5

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(80\%\) số điểm): \(n \le 5000\).

Nguồn: 3D'21