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

Казак Вус, возвращаясь домой с железной дороги, заметил дерево и придумал задачу.

Дано дерево с $n$ вершинами, где каждое ребро имеет определённый вес. Изначально все вершины дерева белые. Ребро называется ярким, если оно соединяет две белые вершины. Вам нужно ответить на $m$ запросов:

• Какое минимальное количество вершин нужно перекрасить в чёрный цвет, чтобы суммарный вес всех ярких рёбер не превышал $k_i$?

Помогите Казаку Вусу решить эту задачу.

Входные данные

Первая строка содержит три целых числа $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$).

Выходные данные

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

Примеры

Примечание

В первом примере, если $k_i\ge 5$, можно оставить все вершины белыми, тогда все рёбра будут яркими, и сумма их весов составит $5$. Если $k_i\le 4$, можно покрасить вершину номер $1$ в чёрный цвет, тогда ярких рёбер не будет, и сумма весов будет равна $0$. В обоих случаях сумма весов ярких рёбер не превышает $k_i$, и перекрашено минимальное количество вершин.

Оценивание

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$ балла): без дополнительных ограничений.