Một đêm mưa lớn kéo qua khu rừng cổ, làm hệ thống đèn hiệu dẫn đường bị tắt gần hết, khiến PhuocThien và uou không thể tìm được lối đi an toàn giữa các trạm quan sát. Theo bản đồ cũ của khu rừng, có \(n\) trạm được nối với nhau bằng \(n - 1\) con đường hai chiều và toàn bộ mạng lưới tạo thành một cây. Trạm số \(1\) là trạm trung tâm, nơi lưu trữ nguồn năng lượng chính để khởi động lại hệ thống. Mỗi trạm \(i\) có hai giá trị đi kèm là năng lượng \(a_i\) và độ tin cậy \(c_i\). Nếu một trạm được chọn để kích hoạt, nó sẽ đóng góp đúng \(a_i\) điểm năng lượng cho hệ thống. Tuy nhiên, không phải trạm nào cũng có thể được chọn một cách độc lập, vì mọi trạm được chọn phải tạo thành một tập hợp liên thông và bắt buộc phải chứa trạm \(1\). Ngoài ra, để tránh làm quá tải mạng lưới, tổng độ tin cậy của các trạm được chọn không được vượt quá \(m\). PhuocThien muốn chọn đúng \(k\) trạm sao cho tập được chọn vừa liên thông, vừa chứa trạm \(1\), vừa có tổng độ tin cậy không vượt quá giới hạn, và tổng năng lượng thu được là lớn nhất có thể. Nếu có nhiều cách chọn hợp lệ, chỉ cần in ra giá trị lớn nhất của tổng năng lượng. Nếu không tồn tại cách chọn nào thỏa mãn, hãy in ra -1. uou còn nhắc rằng những trạm ở xa trạm trung tâm vẫn có thể được chọn, nhưng chỉ khi toàn bộ các trạm nằm trên đường đi từ trạm đó về trạm \(1\) cũng đều được chọn. Điều đó làm cho bài toán trở nên đặc biệt vì không phải cứ chọn các trạm có giá trị lớn nhất là đủ. Một số trạm có thể mang năng lượng âm, nên việc chọn thêm một trạm không phải lúc nào cũng có lợi. Có thể có những trường hợp giới hạn độ tin cậy khiến việc chọn đủ \(k\) trạm trở nên rất khó, thậm chí không thể thực hiện được. Hãy giúp PhuocThien khởi động lại chiếc đèn hiệu cuối cùng của khu rừng cổ.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(k\), \(m\) (\(1 \le k \le n \le 2500, 1 \le m \le 2500\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)), lần lượt là năng lượng của các trạm.
• Dòng thứ ba chứa \(n\) số nguyên \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 1000\)), lần lượt là độ tin cậy của các trạm.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\), \(u \ne v\)), mô tả một con đường hai chiều giữa hai trạm.
• Dữ liệu đảm bảo các con đường tạo thành một cây liên thông.

Output

• In ra một số nguyên duy nhất là tổng năng lượng lớn nhất có thể đạt được khi chọn đúng \(k\) trạm thỏa mãn mọi điều kiện.
• Nếu không tồn tại cách chọn hợp lệ, in ra -1.

Example

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

24

5 4 3
10 20 30 40 50
2 2 2 2 2
1 2
1 3
3 4
3 5

-1

Scoring

• Subtask \(1\) (\(20\) điểm): \(1 \le n \le 20\), \(1 \le k \le n\), \(1 \le m \le 20\).
• Subtask \(2\) (\(30\) điểm): \(1 \le n \le 200\), \(1 \le k \le 50\), \(1 \le m \le 200\).
• Subtask \(3\) (\(50\) điểm): Không có ràng buộc gì thêm.