Cossack Vus and the Tree

Input

The first line contains three integers $n$, $m$, and $g$ (1 \leq n \leq 3\,000, 1 \leq m \leq 2 \cdot 10^5, 0 \leq g \leq 6) — representing the number of vertices, the number of queries, and the block number, respectively.

Each of the following n-1 lines contains three integers u_i, v_i, c_i (1 \leq v_i, u_i \leq n, 1 \leq c_i \leq 10^5) — indicating the vertices connected by the edge and its weight.

The fourth line contains $m$ integers k_1, k_2, \dots, k_m (0 \leq k_i \leq 10^9).

Output

Output $m$ integers x_1, x_2, \dots, x_m, where x_i is the answer to the $i$-th query.

Examples

Note

In the first example, if k_i \geq 5, all vertices can remain white, making all edges bright with a total weight of $5$. For k_i \leq 4, painting vertex number $1$ black results in no bright edges, thus the total weight is $0$. In both scenarios, the sum of the weights of the bright edges does not exceed k_i, and the minimum number of vertices is repainted.

Scoring

1. ($5$ points): m=1; it is guaranteed that the answer does not exceed $1$.

2. ($9$ points): m=1; it is guaranteed that the answer does not exceed $2$.

3. ($28$ points): u_i = v_i - 1; n \leq 200.

4. ($14$ points): m=1; n \leq 10;

5. ($21$ points): n \leq 200;

6. ($23$ points): no additional constraints.