题目背景

zrz_orz 赘喜欢二次元辣！！

题目描述

众所周知的是，zrz_orz 是全机房最强的死宅。他甚至使用嘴遁使得 Samcompu 不得不在自己的网站上挂上时崎狂三。（话说 Samcompu 好像醒悟了又把狂三给去掉了。）作为新一代死宅的一员，从电脑壁纸到输入法皮肤，到处都是二次元的痕迹。所以，他经常在梦里梦见一些二次元的角色。

zrz_orz 的梦，是由 $n$ 个点和 $n-1$ 条边构成的连通图。其中有 $m$ 个节点上有一个二次元的角色。对于 zrz_orz 来说，每一个二次元的角色都有一个对应的 $pos_i$ 和 $val_i$ 表示这个角色在图上的哪一个节点以及与之聊天对 zrz_orz 来说会增加多少愉悦值。（由于某种原因，聊天的过程可以不用计入时间。）可惜的是，zrz_orz 每一次做梦都只会做 $tim_i$ 个单位时间。现在请你告诉他，他每一次做梦最多能获得多少愉悦值。

注：

1. zrz_orz 每一次做梦都只会从 $1$ 号节点开始走！
2. 每一次做梦后 zrz_orz 梦境中的图都不会改变！
3. 每一次做完梦之后 zrz_orz 就必须要回到 $\bm1$ 号节点，否则他就会迷失在梦境里！

输入格式

第1行三个正整数 $N,M,T$ 表示图的节点数、二次元角色的数量、做梦的天数。

接下来 $N-1$ 行每行三个正整数 $u_i,v_i,w_i$ 表示第 $i$ 条边连接的两个节点以及 zrz_orz 走过这条边所花费的时间。

接下来 $M$ 行每行两个正整数 $pos_j$ 和 $val_j$ 表示第 $j$ 个二次元角色在节点上的位置以及能给 zrz_orz 带来的愉悦值。

接下来 $T$ 行每行一个正整数 $tim_k$ 表示第 $k$ 天 zrz_orz 做梦的时间。

输出格式

一共 $T$ 行。每一行包括一个正整数表示 zrz_orz 每天最多能获得的最大愉悦值。

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

提示

第一天哪里都去不了。

第二天 $1\to3\to6\to7\to6\to3\to1$ 获得最大愉悦值为 $7$。

第三天所有的地方都可以走一遍。

• 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$。

注意：标记的分数就是这个 Subtask 的分数，每一个 Subtask 必须全对才能得分。Subtask 2 的时限为 1.5s。

$$\color{white} \text{NOIP 2合1}$$