Tom lại đuổi theo Jerry. Jerry muốn tạo lợi thế bằng cách chạy qua những đám chim bồ câu, nơi Tom khó đuổi theo hơn. Jerry đang ở công viên trung tâm Ljubljana, nơi có \(n\) bức tượng đánh số từ \(1\) đến \(n\), nối với nhau bằng \(n-1\) lối đi sao cho có thể đi từ tượng bất kỳ đến mọi tượng khác. Quanh tượng thứ \(i\) có \(p_i\) con chim bồ câu.

Jerry có \(v\) mẩu bánh mì. Khi đến tượng \(i\), trước tiên Jerry gặp số chim hiện có tại đó. Sau đó, nếu muốn, anh có thể thả một mẩu bánh mì. Tất cả chim ở các tượng kề với \(i\) lập tức bay đến tượng \(i\): số chim tại \(i\) tăng thêm tổng số chim ở các tượng kề, còn các tượng kề đó không còn chim. Jerry rời tượng. Việc chim di chuyển xảy ra trước khi Jerry đến tượng tiếp theo, nên số chim vừa bay đến không được tính vào số chim Jerry gặp tại tượng \(i\).

Jerry có thể bắt đầu ở bất kỳ tượng nào, đi qua các lối (không bao giờ đi qua cùng một lối hai lần), rồi rời công viên tại bất kỳ tượng nào. Anh được thả nhiều nhất \(v\) mẩu bánh mì. Sau khi Jerry rời công viên, Tom đi theo đúng tuyến đường đó. Hãy tối đa hóa hiệu giữa tổng số chim Tom gặp và tổng số chim Jerry gặp.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,v\) (\(1\le n\le100000\), \(0\le v\le100\)), lần lượt là số tượng và số mẩu bánh mì.

Dòng thứ hai chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\) (\(0\le p_i\le10^9\)), là số chim ban đầu quanh mỗi tượng.

Mỗi dòng trong \(n-1\) dòng tiếp theo chứa hai số nguyên \(a_i,b_i\) (\(1\le a_i,b_i\le n\)), cho biết có lối đi giữa hai tượng \(a_i\) và \(b_i\).

Dữ liệu ra

In một số nguyên duy nhất là hiệu lớn nhất có thể đạt được.

Ví dụ

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

36

Giải thích

Jerry có thể bắt đầu tại tượng \(6\), gặp \(5\) con chim rồi thả một mẩu bánh mì. Khi đó tượng \(6\) có \(27\) con chim, còn các tượng \(5,7,8,9\) không còn chim. Sau đó Jerry đi đến tượng \(7\), gặp \(0\) con chim rồi thả mẩu bánh mì thứ hai. Tượng \(7\) có \(41\) con chim, còn các tượng \(2,4,6,10\) không còn chim. Jerry rời công viên. Jerry gặp tổng cộng \(5+0=5\) con chim; Tom đi theo cùng tuyến đường và gặp \(0+41=41\) con. Hiệu là \(41-5=36\).

Phân nhóm

1. \(20\) điểm: \(n\le10\).
2. \(20\) điểm: \(n\le1000\).
3. \(30\) điểm: Có một phương án tối ưu bắt đầu tại tượng \(1\).
4. \(30\) điểm: Không có ràng buộc bổ sung.