Có một cây táo rất to đang vào mùa ra quả. Cây táo gồm có \(n\) đỉnh, ở mỗi đỉnh lá có một số lượng quả táo nhất định.

Trọng số của một cây con là tổng số lượng táo của các đỉnh lá thuộc cây con này. Ví dụ, trọng số của cây con chỉ gồm đỉnh lá nào đó sẽ đúng bằng số lượng táo của đỉnh lá đó.

Một cây táo được gọi là cân bằng nếu với mỗi đỉnh \(v\) của cây táo, tất cả các cây con có đỉnh gốc là con trực tiếp của \(v\) đều có cùng trọng số.

Hãy cho biết cần bỏ đi ít nhất bao nhiêu quả táo ra khỏi các đỉnh lá của cây để làm cây cân bằng. Lưu ý rằng luôn tồn tại một cách để làm cây cân bằng đó là bỏ hết toàn bộ số táo.

Input

• Dòng đầu tiên là số nguyên dương \(n\) \((2 \leq n \leq 10^5)\) là số đỉnh của cây.
• Dòng tiếp theo gồm \(n\) số nguyên \(a_1, a_2, \ldots a_n\) \((0 \leq a_i \leq 10^8)\), với \(a_i\) là số táo ở đỉnh \(i\). Dữ liệu đảm bảo \(a_i\) chỉ khác \(0\) nếu \(i\) là đỉnh lá.
• \(n-1\) dòng tiếp là thông tin các cạnh. Mỗi dòng gồm hai số nguyên dương \(u, v\) cho biết có cạnh nối từ đỉnh \(u\) tới đỉnh \(v\) \((1 \leq u, v \leq n, u \neq v)\).
• Các đỉnh được đánh số từ \(1\) tới \(n\). Đỉnh \(1\) là gốc.

Output

• Gồm một số nguyên duy nhất là số lượng táo ít nhất cần loại bỏ để cây cân bằng

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20, 0 \leq a_i \leq 1\).
• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 2000, 0 \leq a_i \leq 1\).
• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 2000\).
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

6
0 0 12 13 5 6
1 2
1 3
1 4
2 5
2 6

6