{"code":"goodbye22cay","name":"Xin Cây","description":"Hưng được [user:stormgamming] cho $1$ cây vô hướng có trọng số, Hưng rất thích cái cây của [user:stormgamming], vì nó quá đẹp nên Hưng đã xin [user:stormgamming] nhưng [user:stormgamming] không dễ dàng cho không như vậy. [user: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$, [user: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.\r\n\r\n#### Input\r\n- 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.\r\n- Dòng thứ $2$ gồm $n$ số nguyên số nguyên thứ $i$ là trọng số của đỉnh $w_i$.\r\n- $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.\r\n\r\n#### Output\r\n- Gồm $1$ số nguyên dương là trọng số tối đa khi có $k$ thiết bị quan sát.\r\n\r\n#### Scoring\r\n - Subtask $1$ ($10\\%$ số điểm): $1 \\le k \\le n \\le 20$, $1 \\le r,w_i \\le 20$.\r\n - Subtask $2$ ($30\\%$ số điểm): $1 \\le k \\le n \\le 50$, $1 \\le r,w_i \\le 50$.\r\n - 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\r\n - Subtask $4$ ($20\\%$ số điểm): $1 \\le n,r \\le 1000$, $1 \\le w_i \\le 10^{6}$, $k \\le 2$.\r\n - 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}$.\r\n\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        20 3 1\r\n        4 12 17 2 16 6 11 9 9 20 2 12 19 8 14 18 15 20 3 8 \r\n        1 2\r\n        1 3\r\n        3 4\r\n        1 5\r\n        2 6\r\n        2 7\r\n        2 8\r\n        7 9\r\n        7 10\r\n        8 11\r\n        10 12\r\n        3 13\r\n        3 14\r\n        1 15\r\n        5 16\r\n        1 17\r\n        11 18\r\n        4 19\r\n        7 20\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        157\r\n        ```","points":2400.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}