题目背景

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就必须要回到1号节点，否则他就会迷失在梦境里！

输入格式

第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->3->6->7->6->3->1获得最大愉悦值为7。

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

Subtask 1(20 pts):

$ 1 \leqslant T \leqslant 10 \qquad 1 \leqslant N \leqslant 1000 \qquad 1 \leqslant M \leqslant 20 \qquad 1 \leqslant tim_k \leqslant 1000$

Subtask 2(40 pts):

$ 1 \leqslant T \leqslant 10^5 \qquad 1 \leqslant N \leqslant 10^5 \qquad 1 \leqslant M \leqslant 20 \qquad 1 \leqslant tim_k \leqslant 10^5$

Subtask 3(40 pts):

$ 1 \leqslant T \leqslant 5*10^4 \qquad 1 \leqslant N \leqslant 5000 \qquad 1 \leqslant M \leqslant 100 \qquad 1 \leqslant tim_k \leqslant 100 \qquad 1 \leqslant w_i \leqslant 5$

For all test points:

$ 1 \leqslant pos_j,u_i,v_i \leqslant N \qquad 1 \leqslant \sum val_j \leqslant 2e9 \qquad 1 \leqslant w_i \leqslant 20 \qquad 1 \leqslant tim_k \leqslant 10^5 $

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