```

Time Limit: 3000 MS    Memory Limit: 65536 K

Description

Farmer John is gathering the cows. His farm contains a network of
N (1 <= N <= 100,000) fields conveniently numbered 1..N and connected
by N-1 unidirectional paths that eventually lead to field 1. The
fields and paths form a tree.

Each field i > 1 has a single one-way, exiting path to field P_i,
and currently contains C_i cows (1 <= C_i <= 1,000,000,000). In
each time unit, no more than M_i (0 <= M_i <= 1,000,000,000) cows
can travel from field i to field P_i (1 <= P_i <= N) (i.e., only
M_i cows can traverse the path).

Farmer John wants all the cows to congregate in field 1 (which has
no limit on the number of cows it may have). Rules are as follows:

* Time is considered in discrete units.

* Any given cow might traverse multiple paths in the same time
unit. However, no more than M_i total cows can leave field i
(i.e., traverse its exit path) in the same time unit.

* Cows never move *away* from field #1.

In other words, every time step, each cow has the choice either to

a) stay in its current field

b) move through one or more fields toward field #1, as long
as the bottleneck constraints for each path are not violated

Farmer John wants to know how many cows can arrive in field 1 by
certain times. In particular, he has a list of K (1 <= K <= 10,000)
times T_i (1 <= T_i <= 1,000,000,000), and he wants to know, for
each T_i in the list, the maximum number of cows that can arrive
at field 1 by T_i if scheduled to optimize this quantity.

Consider an example where the tree is a straight line, and the T_i
list contains only T_1=5, and cows are distibuted as shown:

Locn:      1---2---3---4      <-- Pasture ID numbers
C_i:       0   1   12  12     <-- Current number of cows
M_i:           5   8   3      <-- Limits on path traversal; field
1 has no limit since it has no exit

The solution is as follows; the goal is to move cows to field 1:

Tree:      1---2---3---4
t=0        0   1   12  12     <-- Initial state
t=1        5   4   7   9      <-- field 1 has cows from field 2 and 3
t=2        10  7   2   6
t=3        15  7   0   3
t=4        20  5   0   0
t=5        25  0   0   0

Thus, the answer is 25: all 25 cows can arrive at field 1 by time
t=5.

Input

* Line 1: Two space-separated integers: N and K

* Lines 2..N: Line i (not i+1) describes field i with three
space-separated integers: P_i, C_i, and M_i

* Lines N+1..N+K: Line N+i contains a single integer: T_i

Output

* Lines 1..K: Line i contains a single integer that is the maximum
number of cows that can arrive at field 1 by time T_i.

Sample Input

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

Sample Output

25

Source
usaco JAN11

```