题目描述

Freda在N座花园中饲养了一些小猫~~~ 花园编号为1~N,由N-1条单向的瞬时传送通道连接,其中第i座花园中有Ci只小猫,并有一条单向传送通道通往Pi。保证从任意一个花园都可以到达Freda所在的花园——1号花园。现在Rainbow来参观Freda的小猫,于是Freda想让所有的小猫到1号花园集中。

连接花园的是高科技的瞬时传送通道,因此小猫们在一个单位时间内可以经过任意多条通道。不过花园i到Pi的通道在任意时间最多只能允许Mi只小猫同时通过。由于花园是很大的,所以每座花园都可以容纳下所有的小猫。换言之,每个单位时间,每只小猫可以选择以下两种行动之一:(1)留在当前的花园;(2)经过若干条传送通道向1号花园移动,不过不能超过传送通道的上限Mi。

现在Freda有一张列着M个时刻的表,她想知道在采用最优策略的情况下,每个时刻结束时最多能有多少小猫到达1号花园?

输入格式

第一行两个用空格隔开的整数N和M。

第2~N行每行三个整数Pi、Ci、Mi,其中第i行描述第i个花园的相关信息。

最后M行每行一个整数,表示Freda想要询问的时刻。

输出格式

输出包含M行。对于每个时刻,输出一个整数表示该时刻结束时能够到达1号花园的小猫的最多数量。

样例输入

4 1

1 1 5

2 12 7

3 12 3

5

样例输出

25

数据范围与约定

对于10%的数据,1<=N、Ci、Mi、Ti<=100。

对于40%的数据,1<=Ci、Mi、Ti<=10000。

对于70%的数据,1<=N<=20000。

对于100%的数据,1<=Pi<=N<=100000,1<=M<=10000,1<=Ci、Mi、Ti<=10^9。