Tom và Jerry lại sa đà vào một cuộc đuổi bắt khốc liệt! Jerry chạy vào công viên trung tâm thành phố Ljubljana để lẩn trốn. Lần này, Jerry có ý đồ len lỏi vào một số đàn bồ câu đông đúc nhằm đẩy Tom vào thế khó khăn khi muốn đuổi theo cậu ấy. Công viên có \(n\) bức tượng được đánh số từ \(1\) đến \(n\) và \(n-1\) lối đi không giao nhau để kết nối các bức tượng đó sao cho từ bức tượng nào cũng có thể di chuyển đến một bức tượng bất kỳ khác bằng cách băng qua một số lối đi có sẵn. Có đúng \(p_i\) chú chim bồ câu đang vây quanh bức tượng thứ \(i\). Jerry mang theo \(v\) mẩu bánh mỳ trong túi của cậu ấy. Nếu cậu ấy ném một mẩu bánh mỳ xuống chân bức tượng mà cậu ấy đang đứng cạnh, toàn bộ những chú chim bồ câu từ các bức tượng liền kề sẽ lập tức bay tới để tranh giành mẩu bánh mỳ này. Kết cục là, số lượng chim bồ câu vây quanh bức tượng hiện tại và các bức tượng liền kề với nó sẽ bị thay đổi.

Cuộc đuổi bắt giữa Tom và Jerry sẽ luôn diễn ra theo trình tự như sau: Đầu tiên, Jerry tiến đến bức tượng thứ \(i\) và gặp \(p_i\) chú chim bồ câu. Sau đó, cậu ấy thả một mẩu bánh mỳ xuống dưới và rời khỏi bức tượng này. Những chú chim bồ câu từ các bức tượng liền kề lập tức di chuyển đến bức tượng thứ \(i\) trước khi Jerry kịp chạy tới một trong các bức tượng liền kề đó (vì vậy số lượng chim bồ câu ở bức tượng tiếp theo sẽ không được tính vào tổng số chim bồ câu mà Jerry đã chạm trán).

Jerry có thể tiến vào công viên từ bất kỳ bức tượng nào, sau đó băng qua một số lối đi (nhưng không bao giờ băng qua cùng một lối đi hai lần trở lên), và cuối cùng rời khỏi công viên từ một bức tượng bất kỳ mà cậu ấy muốn. Sau khi Jerry rời khỏi công viên thì Tom mới bắt đầu tiến vào công viên và di chuyển theo lộ trình y hệt Jerry. Vì muốn cắt đuôi Tom nên Jerry nhờ bạn lên kế hoạch rải tối đa \(v\) mẩu bánh mỳ sao cho chênh lệch giữa tổng số chim bồ câu mà Jerry và Tom chạm trán phải là cao nhất có thể. Lưu ý rằng chỉ những chú chi bồ câu mà Jerry gặp sau khi cậu tiến đến một bức tượng nào đó mới được tính vào tổng số chim bồ câu mà cậu chạm trán. Bạn có thể xem phần giải thích test ví dụ để hiểu rõ hơn.

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(v\).

• Dòng thứ nhì chứa \(n\) số nguyên \(p_1\), \(p_2\),..., \(p_n\).

• Dòng thứ \(i\) trong \(n-1\) dòng tiếp theo chứa cặp số nguyên dương \(a_i\) và \(b_i\) mô tả một lối đi nối bức tượng \(a_i\) và bức tượng \(b_i\).

Output

• In ra một số nguyên duy nhất là độ chênh lệch lớn nhất có thể.

Constraints

• \(1\leq n\leq 10^5\), \(0\leq v\leq 100\), \(0\leq p_i\leq 10^9\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n\leq 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(n\leq 1000\).
• Subtask \(3\) (\(30\%\) số điểm): đảm bảo tồn tại một lộ trình tối ưu bắt đầu từ bức tượng \(1\).

Example

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