Cho một cây \(n\) đỉnh, có đỉnh gốc là \(1\), trên đỉnh \(i\) có số \(A_i\).

Tìm tổng lớn nhất của các đỉnh sau khi xóa đi tối đa \(k\) cây con.

Dữ liệu vào

• Dòng đầu tiên gồm \(2\) số nguyên \(n,k\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\) thể hiện có cạnh nối \(u\) và \(v\).

Dữ liệu ra

• In ra tổng lớn nhất.

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le k \le 100\)
• \(1 \le u,v \le n\)
• \(|A_i| \le 10^9\)

Input 1

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

Output

7

Input 2

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

Output 2

6