题目描述

给定一棵大小为 $n$，根为 $1$ 的树，第 $i$ 个节点上有 $C_i$ 个人，每个人都往根节点上跑，但是每条边有容量，第 $i$ 条边在 1s 内只能有 $M_i$ 个人通过。一个人在 1s 内可以通过很多条边。

$q$ 次询问，每次问 $t_i$ 时有多少人到达根节点。

输入格式

第一行：两个整数 $n \ q（1 \le n \le 10^5，1 \le q \le 10^4）$

第 $2$ 至 $n$ 行，每行三个整数 $P_i \ C_i \ M_i \ (1 \le C_i \le 10^9,0 \le M_i \le 10^9,1 \le P_i \le N)$，其中 $P_i$ 表示点 $i$ 有一条连接到 点 $P_i$ 的单向边。

下来 $q$ 个整数 $t_i（1 \le t_i \le 10^9 ）$

输出格式

每行一个答案对应 $t_i$ 。

输入输出样例 #1

输入 #1

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

输出 #1

25

说明/提示