Background

zrz_orz really loves anime (èr cì yuán)!!

Problem Description

As everyone knows, zrz_orz is the strongest hardcore otaku in the whole computer room. He even used “talk-no-jutsu” to make Samcompu put Kurumi Tokisaki on his website. (But it seems Samcompu realized something and removed Kurumi again.) As a member of the new generation of otaku, from desktop wallpapers to input method skins, everything is filled with anime traces. So, he often dreams of some anime characters.

zrz_orz’s dream is a connected graph with $n$ nodes and $n-1$ edges. There are $m$ nodes that have an anime character on them. For zrz_orz, each anime character has a corresponding $pos_i$ and $val_i$, meaning which node this character is on, and how much happiness value zrz_orz gains by chatting with them. (For some reason, the chatting process does not need to be counted in time.) Unfortunately, each time zrz_orz dreams, he only has $tim_i$ units of time. Now please tell him: in each dream, what is the maximum happiness value he can obtain?

Notes:

1. Each time zrz_orz dreams, he will always start from node $1$.
2. After each dream, the graph in zrz_orz’s dream will not change.
3. After each dream, zrz_orz must return to node $\bm1$, otherwise he will get lost in the dream!

Input Format

The first line contains three positive integers $N, M, T$, representing the number of nodes in the graph, the number of anime characters, and the number of days of dreaming.

The next $N-1$ lines each contain three positive integers $u_i, v_i, w_i$, representing that the $i$-th edge connects two nodes, and the time cost for zrz_orz to traverse this edge.

The next $M$ lines each contain two positive integers $pos_j$ and $val_j$, representing the position of the $j$-th anime character and the happiness value it can bring to zrz_orz.

The next $T$ lines each contain one positive integer $tim_k$, representing the dreaming time on the $k$-th day.

Output Format

Output a total of $T$ lines. Each line contains one positive integer, representing the maximum happiness value zrz_orz can obtain on that day.

7 3 3
1 2 2
1 3 1
2 4 1
2 5 10
3 6 1
6 7 2
4 5
5 50
7 7
1
10
100

0
7
62

Hint

On the first day, he cannot go anywhere.

On the second day, taking the route $1\to3\to6\to7\to6\to3\to1$, the maximum happiness value is $7$.

On the third day, he can traverse all places once.

• Subtask 1 (20 pts): $1 \leqslant T \leqslant 10$, $1 \leqslant N \leqslant 1000$, $1 \leqslant M \leqslant 20$, $1 \leqslant tim_k \leqslant 1000$.
• Subtask 2 (40 pts): $1 \leqslant T \leqslant 10^5$, $1 \leqslant N \leqslant 10^5$, $1 \leqslant M \leqslant 20$, $1 \leqslant tim_k \leqslant 10^5$.
• Subtask 3 (40 pts): $1 \leqslant T \leqslant 5\times10^4$, $1 \leqslant N \leqslant 5000$, $1 \leqslant M \leqslant 100$, $1 \leqslant tim_k \leqslant 100$, $1 \leqslant w_i \leqslant 5$.

For all test points: $1 \leqslant pos_j, u_i, v_i \leqslant N$, $1 \leqslant \sum val_j \leqslant 2\times10^9$, $1 \leqslant w_i \leqslant 20$, $1 \leqslant tim_k \leqslant 10^5$.

Note: The marked score is the score of this Subtask. Each Subtask must be completely correct to get the score. The time limit for Subtask 2 is 1.5 s.

Translated by ChatGPT 5