Козак Вус та дерево
Козак Вус побачив дерево, коли повертався додому із залізничної дороги та придумав задачу.
Задане дерево на вершинах, кожне ребро якого має певну вагу. Спочатку всі його вершини білі. Назвемо ребро яскравим, якщо воно з'єднує дві білі вершини. Дайте відповідь на запитів:
Яку найменшу кількість вершин необхідно перефарбувати у чорний колір, щоб сумарна вага всіх яскравих ребер не перевищувала ?
Допоможіть Козаку Вусу розв'язати цю задачу.
Вхідні дані
Перший рядок містить три цілі числа , та (, , ) — кількість вершин, кількість запитів та номер блока.
Кожен з наступних рядків містить по три цілі числа , , (, ) — вершини, які з'єднує ребро, і його вага.
Четвертий рядок містить цілих чисел ().
Вихідні дані
Виведіть цілих чисел , де — відповідь на запит.
Приклади
Примітка
У першому прикладі якщо , то можемо залишити всі вершини білими, тоді всі ребра яскраві і сума їхніх ваг рівна . Для можемо пофарбувати вершину номер у чорний колір, тоді яскравих ребер не буде, а отже сума ваг рівна . В обох цих випадках сума ваг яскравих ребер не перевищує і перефарбовано мінімальну кількість вершин.
Оцінювання
( балів): ; гарантується, що відповідь не перевищує .
( балів): ; гарантується, що відповідь не перевищує .
( балів): ; .
( балів): ; ;
( бал): ;
( бали): без додаткових обмежень.