Козак Вус та дерево

Козак Вус побачив дерево, коли повертався додому із залізничної дороги та придумав задачу.

Задане дерево на $n$ вершинах, кожне ребро якого має певну вагу. Спочатку всі його вершини білі. Назвемо ребро яскравим, якщо воно з'єднує дві білі вершини. Дайте відповідь на $m$ запитів:

• Яку найменшу кількість вершин необхідно перефарбувати у чорний колір, щоб сумарна вага всіх яскравих ребер не перевищувала $k_i$?

Допоможіть Козаку Вусу розв'язати цю задачу.

Input

Перший рядок містить три цілі числа $n$, $m$ та $g$ ($1\le n\le 3000$, $1\le m\le 2\cdot 10^5$, $0\le g\le 6$) — кількість вершин, кількість запитів та номер блока.

Кожен з наступних $n-1$ рядків містить по три цілі числа $u_i$, $v_i$, $c_i$ ($1\le v_i,u_i\le n$, $1\le c_i\le 10^5$) — вершини, які з'єднує ребро, і його вага.

Четвертий рядок містить $m$ цілих чисел $k_1,k_2,\dots ,k_m$ ($0\le k_i\le 10^9$).

Output

Виведіть $m$ цілих чисел $x_1,x_2,\dots ,x_m$, де $x_i$ — відповідь на $i-й$ запит.

Examples

Note

У першому прикладі якщо $k_i\ge 5$, то можемо залишити всі вершини білими, тоді всі ребра яскраві і сума їхніх ваг рівна $5$. Для $k_i\le 4$ можемо пофарбувати вершину номер $1$ у чорний колір, тоді яскравих ребер не буде, а отже сума ваг рівна $0$. В обох цих випадках сума ваг яскравих ребер не перевищує $k_i$ і перефарбовано мінімальну кількість вершин.

Scoring

1. ($5$ балів): $m=1$; гарантується, що відповідь не перевищує $1$.

2. ($9$ балів): $m=1$; гарантується, що відповідь не перевищує $2$.

3. ($28$ балів): $u_i=v_i-1$; $n\le 200$.

4. ($14$ балів): $m=1$; $n\le 10$;

5. ($21$ бал): $n\le 200$;

6. ($23$ бали): без додаткових обмежень.