题目描述

$\red{Farmer John}$有一张$\red{N}$个农场构成的网络$\red{(1 <= N <= 100,000) ，}$我们将农场标记为$\red{1...N}$。 农场被$\red{N-1}$条单向道路连接，保证从任何一个 农成以到达$\red{1}$号农场。$\red{FJ}$想让奶牛到$\red{1}$号农场集中 （$\red{P.S. }$至于要做什么我也不知道）。

对于每个农场$\red{i > 1}$都有一条单独的单向道路通往$\red{P_i，}$并且这个农场里有$\red{C_i}$只奶牛 （$\red{1 <= C_i <= 1,000,000,000}$）。在每个单位时间里，这条道路允许不超过$\red{M_i (0 <= M_i <= 1,000,000,000)}$只奶牛从农场$\red{i}$走到农场$\red{P_i (1 <= P_i <= N)}$。 $\red{Farmer John }$想让所有的奶牛都集中在$\red{1}$号农场（农场容纳奶牛的数量是没有限制的）。

下面是奶牛集中到$\red{1}$号农场过程的规则：

$\red{* }$我们认为时间是离散的

$\red{* }$任何奶牛都可以在一个单位时间里走过任意多条道路。

但是，必须满足每条道路的上限$\red{M_i}$。

$\red{* }$奶牛从来不会离开$\red{1}$号农场。 换句话说，每一个单位时间，每只奶牛可以选择下面行动之一：

$\red{a)}$留在当前的农场

$\red{b)}$经过一条或者多条道路，向$\red{1}$号农场移动。

同样，需要满足每条道路的上限$\red{M_i}$。

$\red{FJ}$想知道有多少奶牛可以在某个特定的时刻到达$\red{1}$号农场。特别的，他有一张列着$\red{K (1 <= K <= 10,000) }$个时间$\red{T_i (1 <= T_i <= 1,000,000,000)}$的单子，他想知道对于每个$\red{T_i，}$如果采用最优 的策略在这个时刻结束时最多能有多少奶牛到达$\red{1}$号农场。 考虑如下一个样例（树退化成链），列表里只有$\red{T_1=5}$一个时刻，奶牛如下分布：

输入格式

第$\red{1}$行：两个空格隔开的整数$\red{N}$和$\red{K }$

第$\red{2}$到$\red{N}$行：第$\red{i}$行包含三个空格隔开的整数，表示农场$\red{i（}$不是$\red{i+1）}$的$\red{P_i，}$$\red{C_i，}$$\red{M_i }$

第$\red{N+1}$到$\red{N+K}$行：第$\red{N+i}$行包含一个整数$\red{T_i}$

输出格式

第$\red{1}$到$\red{K}$行：第$\red{i}$行包含一个整数，表示到$\red{T_i}$个单位时间为止能够到达$\red{1}$号农场奶牛的最多数量。

样例

输入样例

4 1
1 1 5
2 12 7
3 12 3
5

输出样例

25