Truy vấn max

Cho một cây có trọng số gồm \(n\) đỉnh. Cây là một đồ thị vô hướng liên thông không có chu trình.

Có \(m\) truy vấn, truy vấn thứ \(i\) là một số nguyên dương \(q_{i}\). Mỗi truy vấn bạn cần trả lời có bao nhiêu cặp \((u, v) (u < v)\) mà cạnh có trọng số lớn nhất trên đường đi từ đỉnh \(u\) đến đỉnh \(v\) có giá trị không vượt quá \(q_{i}\).

Input

Dòng đầu tiên gồm hai số nguyên dương \(n, m\) - số lượng đỉnh và số lượng truy vấn.

\(n - 1\) dòng tiếp theo, mỗi dòng gồm \(3\) số \(x, y, w\) - có cạnh nối đỉnh x và đỉnh y, cạnh đó có trọng số là \(w\). \((x, y <= n, w <= 10^9)\)

Dòng cuối cùng gồm \(m\) số nguyên dương \(q_{1}, q_{2}, ... , q_{m}\). \((q_{i} <= 10^9)\)

Output

Gồm \(m\) số, mỗi số cách nhau một dấu cách, là kết quả của các truy vấn.

Example

7 5
1 2 1
3 2 3
2 4 1
4 5 2
5 7 4
3 6 2
5 2 3 4 1

21 7 15 21 3 

1 2
1 2

0 0 

3 3
1 2 1
2 3 2
1 3 2

1 3 3 

Scoring

Có \(25\) phần trăm số test có \(n, m <= 20\)

Có \(25\) phần trăm số test có \(n, m <= 500\)

Có \(50\) phần trăm số test có \(n, m <= 2.10^5\)