Problem: You are given a weighted tree consisting of n vertices. Recall that a tree is a connected graph without cycles. Vertices u_i and v_i are connected by an edge with weight w_i.

You are given m queries. The i-th query is given as an integer q_i. In this query you need to calculate the number of pairs of vertices (u, v) (u < v) such that the maximum weight of an edge on a simple path between u and v doesn't exceed q_i.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 2 ⋅ 10^5) — the number of vertices in the tree and the number of queries.

Each of the next n - 1 lines describes an edge of the tree. Edge i is denoted by three integers u_i, v_i and w_i — the labels of vertices it connects (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) and the weight of the edge (1 ≤ w_i ≤ 2 ⋅ 10^5). It is guaranteed that the given edges form a tree.

The last line of the input contains m integers q_1, q_2, ..., q_m (1 ≤ q_i ≤ 2 ⋅ 10^5), where q_i is the maximum weight of an edge in the i-th query.

Output

Print m integers — the answers to the queries. The i-th value should be equal to the number of pairs of vertices (u, v) (u < v) such that the maximum weight of an edge on a simple path between u and v doesn't exceed q_i.

Queries are numbered from 1 to m in the order of the input.

Examples

Input


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


Output


21 7 15 21 3 


Input


1 2
1 2


Output


0 0 


Input


3 3
1 2 1
2 3 2
1 3 2


Output


1 3 3 

Note

The picture shows the tree from the first example: <image>

Solution (in PYTHON):

Solution:
from sys import stdin
from collections import *


def arr_sum(arr):
    tem = [0]
    for i in range(len(arr)):
        tem.append(tem[i] + arr[i])
    return tem


class disjointset:
    def __init__(self, n):
        self.rank, self.parent, self.nsets = [0] * (n + 1), [i for i in range(n + 1)], [1] * (n + 1)

    def find(self, x):
        xcopy = x
        while x != self.parent[x]:
            x = self.parent[x]

        while xcopy != x:
            self.parent[xcopy], xcopy = x, self.parent[xcopy]

        return x

    def union(self, x, y):
        xpar, ypar = self.find(x), self.find(y)

        # already union
        if xpar == ypar:
            return
        # perform union by rank
        par, child = xpar, ypar
        if self.rank[xpar] < self.rank[ypar]:
            par, child = ypar, xpar

        elif self.rank[xpar] == self.rank[ypar]:
            self.rank[xpar] += 1

        self.parent[child] = par
        self.nsets[par] += self.nsets[child]

    # find min total weight tree
    def kruskal(self):
        mem, cur, lst = [0] * Max, 0, edges[0][-1]

        # loop over v-1
        for i in range(len(edges)):
            u, v, w = edges[i]
            if w != lst:
                mem[lst] = cur
                lst = w

            upar, vpar = self.find(u), self.find(v)

            # no cycle
            if upar != vpar:
                su = self.nsets[upar] + self.nsets[vpar]
                cur -= (self.nsets[upar] * (self.nsets[upar] - 1)) // 2
                cur -= (self.nsets[vpar] * (self.nsets[vpar] - 1)) // 2
                cur += (su * (su - 1)) // 2
                self.union(upar, vpar)

        mem[lst] = cur
        for i in range(1, Max):
            if not mem[i]:
                mem[i] = mem[i - 1]

        print(' '.join(map(str, [mem[i] for i in qur])))


Max = 2 * 10 ** 5 + 1
rints = lambda: [int(x) for x in stdin.readline().split()]
n, m = rints()
edges = sorted([rints() for _ in range(n - 1)], key=lambda x: x[2])
qur = rints()
dis = disjointset(n)
if n == 1:
    print(' '.join(['0'] * m))
else:
    dis.kruskal()