Козак Вус побачив дерево, коли повертався додому із залізничної дороги та придумав задачу.
Задане дерево на $$$n$$$ вершинах, кожне ребро якого має певну вагу. Спочатку всі його вершини білі. Назвемо ребро яскравим, якщо воно з'єднує дві білі вершини. Дайте відповідь на $$$m$$$ запитів:
Допоможіть Козаку Вусу розв'язати цю задачу.
Перший рядок містить три цілі числа $$$n$$$, $$$m$$$ та $$$g$$$ ($$$1 \leq n \leq 3\,000$$$, $$$1 \leq m \leq 2 \cdot 10^5$$$, $$$0 \leq g \leq 6$$$) — кількість вершин, кількість запитів та номер блока.
Кожен з наступних $$$n-1$$$ рядків містить по три цілі числа $$$u_i$$$, $$$v_i$$$, $$$c_i$$$ ($$$1 \leq v_i, u_i \leq n$$$, $$$1 \leq c_i \leq 10^5$$$) — вершини, які з'єднує ребро, і його вага.
Четвертий рядок містить $$$m$$$ цілих чисел $$$k_1, k_2, \dots, k_m$$$ ($$$0 \leq k_i \leq 10^9$$$).
Виведіть $$$m$$$ цілих чисел $$$x_1, x_2, \dots, x_m$$$, де $$$x_i$$$ — відповідь на $$$i-й$$$ запит.
3 5 0 1 2 3 1 3 2 3 5 1 2 0
1 0 1 1 1
4 4 0 1 3 10 2 1 15 1 4 50 75 50 72 19
0 1 1 1
5 8 0 1 4 5 2 1 18 1 3 9 3 5 27 5 15 7 19 20 58 35 27
2 2 2 2 2 1 1 1
У першому прикладі якщо $$$k_i \geq 5$$$, то можемо залишити всі вершини білими, тоді всі ребра яскраві і сума їхніх ваг рівна $$$5$$$. Для $$$k_i \leq 4$$$ можемо пофарбувати вершину номер $$$1$$$ у чорний колір, тоді яскравих ребер не буде, а отже сума ваг рівна $$$0$$$. В обох цих випадках сума ваг яскравих ребер не перевищує $$$k_i$$$ і перефарбовано мінімальну кількість вершин.