Description

Farmer John 正在聚集他的奶牛。他的农场包含了一个网络，这个网络由 $N(1\le N\le10^5)$ 块编号从 $1$ 到 $N$ 的田地构成，田地之间由 $N-1$ 条有向的路径连接，保证从每块田地出发都能到达 $1$ 号田地。这些田地和路径形成了一棵树的结构。

每块满足编号大于 $1$ 的田地 $i$ 有一条有向路径连向 $P_i(1\le P_i\le N)$，同时这块田地上面有 $C_i(1\le C_i\le10^9)$ 头奶牛。在每个单位时间内，最多 $M_i(0\le M_i\le10^9)$ 头奶牛可以通过从 $i$ 连向 $P_i$ 的这条路径。

Farmer John 想要让所有的奶牛集合到没有奶牛数量限制的田地 $1$ 上。但是这一过程要符合以下规则：

• 时间是离散的。

• 任何给定的奶牛在同一时间单位内都可能穿过多条路径。但在每个单位时间内，最多 $M_i(0\le M_i\le10^9)$ 头奶牛可以通过从 $i$ 连向 $P_i$ 的这条路径。

• 奶牛不会从田地 $1$ 离开。

换句话说，每一时刻，奶牛都必须从以下几项中选择一项：

• 在它现在所在的田地里待着；

• 沿着路径向着田地 $1$ 经过一块或多块田地，同时不能违反每条路径的 $M_i$ 的限制。

Farmer John 想要知道在特定时间内有多少奶牛可以到达田地 $1$。具体的，他有一个包含了 $K(1\le K\le10^4)$ 个时间 $T_i(1\le T_i\le 10^9)$ 的列表，他想要知道，对于每一个列表中的 $T_i$，最多有多少头奶牛可以在 $T_i$ 时间内到达田地 $1$。

Input Format

第一行：两个用空格分隔的整数：$N$ 和 $K$。

第 $2$ 至 $N$ 行：第 $i$ 行用三个用空格分隔的整数描述了田地 $i$：$P_i$，$C_i$ 和 $M_i$。

第 $N+1$ 至 $N+K$ 行：第 $N+i$ 行包含一个整数：$T_i$。

Output Format

第 $1$ 至 $K$ 行：第 $i$ 行包含一个整数，表示可以在 $T_i$ 时间内到达田地 $1$ 的奶牛的数量的最大值。

translated by 350558

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

25 

Hint

$1\le P_i\le N\le10^5$，$1\le C_i,T_i\le10^9$，$0\le M_i\le10^9$，$1\le K\le10^4$。