Козак Вус побачив дерево, коли повертався додому із залізничної дороги та придумав задачу.
Задане дерево на n вершинах, кожне ребро якого має певну вагу. Спочатку всі його вершини білі. Назвемо ребро яскравим, якщо воно з'єднує дві білі вершини. Дайте відповідь на m запитів:
Яку найменшу кількість вершин необхідно перефарбувати у чорний колір, щоб сумарна вага всіх яскравих ребер не перевищувала ki?
Допоможіть Козаку Вусу розв'язати цю задачу.
Перший рядок містить три цілі числа n, m та g (1≤n≤3000, 1≤m≤2⋅105, 0≤g≤6) — кількість вершин, кількість запитів та номер блока.
Кожен з наступних n−1 рядків містить по три цілі числа ui, vi, ci (1≤vi,ui≤n, 1≤ci≤105) — вершини, які з'єднує ребро, і його вага.
Четвертий рядок містить m цілих чисел k1,k2,…,km (0≤ki≤109).
Виведіть m цілих чисел x1,x2,…,xm, де xi — відповідь на i−й запит.
У першому прикладі якщо ki≥5, то можемо залишити всі вершини білими, тоді всі ребра яскраві і сума їхніх ваг рівна 5. Для ki≤4 можемо пофарбувати вершину номер 1 у чорний колір, тоді яскравих ребер не буде, а отже сума ваг рівна 0. В обох цих випадках сума ваг яскравих ребер не перевищує ki і перефарбовано мінімальну кількість вершин.
(5 балів): m=1; гарантується, що відповідь не перевищує 1.
(9 балів): m=1; гарантується, що відповідь не перевищує 2.
(28 балів): ui=vi−1; n≤200.
(14 балів): m=1; n≤10;
(21 бал): n≤200;
(23 бали): без додаткових обмежень.