Một mạng máy tính nội bộ của một tổ chức khủng bố gồm \(N\) thiết bị được đánh số từ \(1\) đến \(N\). Các thiết bị được kết nối bởi \(N-1\) dây cáp sao cho hai thiết bị bất kì đều được kết nối với nhau thông qua một số đoạn cáp. Cáp thứ \(i\) kết nối thiết bị \(u_i\) và \(v_i\).

Mỗi thiết bị \(j\) \((1 \le j \le N)\) có một thông số \(A_j\) \((A_j \neq 0)\):

• Nếu \(A_j < 0\), thiết bị là một máy tính có mức tiêu thụ điện là \(-A_j\).
• Nếu \(A_j > 0\), thiết bị là một nguồn điện có công suất \(A_j\).

Để triệt phá hệ thống mạng này, bạn cần ngắt kết nối một số đoạn cáp. Khi đó hệ thống mạng sẽ được chia thành các thành phần liên thông. Hệ thống sẽ bị vô hiệu hóa hoàn toàn nếu như tất cả các thành phần liên thông thỏa mãn một trong hai điều kiện sau:

• Thành phần liên thông không chứa máy tính: tất cả các thiết bị \(j\) trong thành phần đều có \(A_j > 0\).
• Thành phần liên thông không cung cấp đủ điện: tổng \(A_j\) của các thiết bị \(j\) trong thành phần nhỏ hơn \(0\).

Hãy xác định cần ngắt kết nối ít nhất bao nhiêu đoạn cáp để vô hiệu hóa hoàn toàn hệ thống.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \le N \le 3000)\) - số lượng thiết bị trong hệ thống;
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) \((1 \le |A_i| \le 10^9)\) - thông số của mỗi thiết bị;
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i\) và \(v_i\) \((1 \le u_i, v_i \le N, u_i \neq v_i)\) - số thứ tự của hai thiết bị mà dây cáp thứ \(i\) kết nối.

Output

• In ra số lượng dây cáp ít nhất cần ngắt kết nối để vô hiệu hóa hệ thống.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 300, |A_i| = 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(|A_i| = 1\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 300\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 2 3 4
1 2
1 3
1 4

0

6
10 -1 10 -1 10 -1
1 2
2 3
3 4
4 5
5 6

5

8
-2 3 6 -2 -2 -5 3 2
3 4
7 6
6 2
8 2
5 3
1 8
3 7

3