Hưng được stormgamming cho \(1\) cây vô hướng có trọng số, Hưng rất thích cái cây của stormgamming, vì nó quá đẹp nên Hưng đã xin stormgamming nhưng stormgamming không dễ dàng cho không như vậy. stormgamming cho Hưng \(k\) thiết bị quan sát, thiết bị quan sát sẽ được gắn trên một đỉnh của cây và có thể quan sát các đỉnh khác nó trong phạm vi \(\le r\), stormgamming cần biết trọng số tối đa khi có \(k\) thiết bị quan sát, một đỉnh có thể được quan sát bởi nhiều thiết bị và trọng số được lấy chỉ tính \(1\) lần, vì Hưng quá non nên không thể tìm được nên cần đến sự trợ giúp của bạn.

Input

• Dòng đầu tiên gồm \(3\) số nguyên dương \(n, k, r\) lần lượt là số đỉnh của cây, số thiết bị quan sát, phạm vi quan sát của mỗi thiết bị quan sát.
• Dòng thứ \(2\) gồm \(n\) số nguyên số nguyên thứ \(i\) là trọng số của đỉnh \(w_i\).
• \(n-1\) dòng tiếp theo gồm \(2\) số nguyên dương \(u, v\) \(-\) mô tả \(1\) cạnh trên cây.

Output

• Gồm \(1\) số nguyên dương là trọng số tối đa khi có \(k\) thiết bị quan sát.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \le k \le n \le 20\), \(1 \le r,w_i \le 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le k \le n \le 50\), \(1 \le r,w_i \le 50\).
• Subtask \(3\) (\(10\%\) số điểm): \(1 \le k \le n \le 1000\), \(1 \le r \le 1000\), \(0 \le w_i \le 10^{6}\), cây tạo thành \(1\) đường thẳng
• Subtask \(4\) (\(20\%\) số điểm): \(1 \le n,r \le 1000\), \(1 \le w_i \le 10^{6}\), \(k \le 2\).
• Subtask \(5\) (\(30\%\) số điểm): \(1 \le k \le n \le 1000\), \(1 \le r \le 1000\), \(0 \le w_i \le 10^{6}\).

Example

20 3 1
4 12 17 2 16 6 11 9 9 20 2 12 19 8 14 18 15 20 3 8 
1 2
1 3
3 4
1 5
2 6
2 7
2 8
7 9
7 10
8 11
10 12
3 13
3 14
1 15
5 16
1 17
11 18
4 19
7 20

157