The Robotics Olympiad teams were competing in a contest.
There was a tree drawn on the floor, consisting of n nodes and n - 1 edges. The nodes are numbered from 1 to n, and each edge has a weight. The tree is rooted at the first node. q teams are participating, and each team is given an integer xi. Their robot should start at node 1, and move in the following way until there are no valid moves left: From all the edges between the current node and it's children, go through the edge with the maximum value less than xi. Note that the robot can't move to the parent, only to children.
However, the teams weren't able to program the robots to return to them after the contest, so they had to manually pick them up. Since the tree can be quite large, they need your help to determine where each robot ended it's movement.
The first line contains a single integer T, the number of test cases.
The first line of each test case contains two space-separated integers n and q. (1 ≤ n, q ≤ 105).
The following n - 1 lines contain 3 integers ui, vi, wi. This means that there is an edge connecting nodes ui and vi, with weight wi. (1 ≤ ui, vi ≤ n) (1 ≤ wi ≤ 109). It's guaranteed that all wi are distinct.
The following line contains q integers xi. (1 ≤ xi ≤ 109).
For each test case, print one line with a single number Si, the sum of numbers of nodes where each robot ends.
In the sample test case, the robots end in the following nodes: {1, 1, 2, 5, 5, 3, 4}.
Si = 1+1+2+5+5+3+4 = 21.
Large I/O files. Please consider using fast input/output methods.
## Input
The first line contains a single integer T, the number of test cases. The first line of each test case contains two space-separated integers n and q. (1 ≤ n, q ≤ 105). The following n - 1 lines contain 3 integers ui, vi, wi. This means that there is an edge connecting nodes ui and vi, with weight wi. (1 ≤ ui, vi ≤ n) (1 ≤ wi ≤ 109). It's guaranteed that all wi are distinct.The following line contains q integers xi. (1 ≤ xi ≤ 109).
## Output
For each test case, print one line with a single number Si, the sum of numbers of nodes where each robot ends.
[samples]
## Note
In the sample test case, the robots end in the following nodes: {1, 1, 2, 5, 5, 3, 4}. Si = 1+1+2+5+5+3+4 = 21.Large I/O files. Please consider using fast input/output methods.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $, let three fractions be given as $ \frac{n_{k,1}}{d_{k,1}}, \frac{n_{k,2}}{d_{k,2}}, \frac{n_{k,3}}{d_{k,3}} $, where $ n_{k,i}, d_{k,i} \in \mathbb{Z}^+ $ and $ 1 \leq n_{k,i}, d_{k,i} \leq 10^6 $.
**Constraints**
1. $ 1 \leq T \leq 10^3 $
2. For each $ k \in \{1, \dots, T\} $ and $ i \in \{1,2,3\} $:
$ 1 \leq n_{k,i} \leq 10^6 $, $ 1 \leq d_{k,i} \leq 10^6 $
**Objective**
For each test case $ k $, compute the sum:
$$
S_k = \frac{n_{k,1}}{d_{k,1}} + \frac{n_{k,2}}{d_{k,2}} + \frac{n_{k,3}}{d_{k,3}}
$$
and output the result as a simplified fraction $ \frac{\text{num}}{\text{den}} $, where $ \gcd(\text{num}, \text{den}) = 1 $.