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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main
{
    static Edge [][] adjList ;
    static Compressor comp ;
    static int [] depth , size ;
    static long [] ans ;
    static int [] tot , equal ;

    static void update(int x , int val , int [] ft)
    {
        for(int i = x ; i < ft.length ; i += i & -i)
            ft[i] += val ;
    }

    static int query(int x , int [] ft)
    {
        int ans = 0 ;
        for( ; x > 0 ; x ^= x & -x)
            ans += ft[x] ;
        return ans ;
    }
    static int rsq(int l , int r , int [] ft)
    {
        return query(r , ft) - query(l - 1 , ft) ;
    }

    static int getSize(int u , int p , int lb)
    {
        size[u] = 1 ;
        for(Edge e : adjList[u])
            if(e.to != p && depth[e.to] == -1)
            {
                size[u] += getSize(e.to, u , lb);
                comp.add(e.cost , lb) ;
                comp.add(e.cost - 1 , lb);
            }
        return size[u] ;
    }

    static int getCentroid(int u , int p , int n)
    {
        for(Edge e : adjList[u])
            if(e.to != p && depth[e.to] == -1 && size[e.to] * 2 > n)
                return getCentroid(e.to , u , n) ;
        return u ;
    }
    static void addAll(int u)
    {
        for(Edge e : adjList[u])
            if(depth[e.to] == -1)
                add(e.to , u , e.cost , true);
    }
    static void add(int u , int p , int dist , boolean f)
    {

        update(comp.get(dist) , 1 , tot);
        if(f)
            update(comp.get(dist) , 1 , equal);

        for(Edge e : adjList[u])
            if(e.to != p && depth[e.to] == -1)
                add(e.to , u , Math.max(dist , e.cost) , f);

    }
    static void clear(int u , int p , int dist)
    {
        update(comp.get(dist) , -1 , tot);
        update(comp.get(dist) , -1 , equal);

        for(Edge e : adjList[u])
            if(e.to != p && depth[e.to] == -1)
                clear(e.to , u , Math.max(dist , e.cost));

    }
    static void computeDist(int u , int  p , int dist)
    {
        ans[dist] ++ ;
        ans[dist] += query(comp.get(dist - 1) ,tot) ;
        ans[dist] += rsq(comp.get(dist) , comp.get(dist) , equal) ;

        for(Edge e : adjList[u])
            if(e.to != p && depth[e.to] == -1)
                computeDist(e.to , u , Math.max(dist , e.cost));
    }

    static void decompose(int u  , int lb)
    {
        end = 0 ;
        comp = new Compressor() ;
        int maxSize = getSize(u , -1 , lb) ;
        u = getCentroid(u , -1 , maxSize) ;
        depth[u] = lb ;

        maxSize = Math.max(maxSize , comp.fix() + 1);

        tot = new int [maxSize + 1] ;
        equal = new int [maxSize + 1];
        addAll(u);

        for(Edge e : adjList[u])
            if(depth[e.to] == -1)
            {
                clear(e.to , u , e.cost);
                computeDist(e.to , u , e.cost);
                add(e.to , u , e.cost , false);
            }

        for(Edge e : adjList[u])
            if(depth[e.to] == -1)
                decompose(e.to , lb + 1);
    }

    public static void main (String [] args) throws Exception
    {
        Scanner sc = new Scanner() ;
        PrintWriter out = new PrintWriter(System.out) ;
        int n = sc.nextInt() ;
        int m = sc.nextInt() ;
        int N = n ;
        int [] x = new int [N - 1] , y = new int[N - 1] , w = new int [N - 1];
        int [] deg = new int [N] ;
        for(int i = 0 ;i < N - 1; i++)
        {
            deg[x[i] = sc.nextInt() - 1] ++ ;
            deg[y[i] = sc.nextInt() - 1] ++ ;
            w[i] = sc.nextInt() ;
        }
        adjList = new Edge [n][] ;
        for(int i = 0 ;i < N ;i++) adjList[i] = new Edge [deg[i]] ;
        for(int i = 0 ; i < N - 1 ;i++)
        {
            adjList[x[i]][--deg[x[i]]] = new Edge(y[i] , w[i]) ;
            adjList[y[i]][--deg[y[i]]] = new Edge(x[i] , w[i]) ;
        }
        ans = new long [(int)2e5 + 1] ;
        depth = new int [n] ;
        size = new int [n] ;
        Arrays.fill(depth , -1);
        decompose(0 , 0);
        for(int i = 1 ; i <= 2e5 ; i ++)
            ans[i] += ans[i - 1] ;
        while (m-->0)
            out.println(ans[sc.nextInt()]);
        out.flush();
    }
    static class Edge
    {
        int to ;
        int cost ;

        Edge(int a , int b)
        {
            to = a ;
            cost = b ;
        }
    }

    static int [] map = new int [(int)2e5 + 1];
    static int [] set = new int [(int)2e5 + 1] ;
    static int [] tin = new int [(int)2e5 + 1] ;
    static int  end ;
    static class Compressor
    {
        HashSet<Integer> tin = new HashSet<>(); 
        
        void add(int x ,int lb)
        {
            if(tin.contains(x))return;
            set[end++] = x ;
            tin.add(x) ; 
        }
        int fix()
        {
            int cnt = 0 ;
            Arrays.sort(set , 0 , end);
            for(int i  = 0 ; i < end ; i ++)
                map[set[i]] = ++cnt;
            return cnt ;
        }
        int get(int x)
        {
            return map[x] ;
        }
    }
    static class Scanner
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ;
        StringTokenizer st ;

        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine()) ;
            return st.nextToken() ;
        }
        int nextInt() throws Exception
        {
            return Integer.parseInt(next()) ;
        }
        long nextLong () throws Exception
        {
            return Long.parseLong(next()) ;
        }
    }

}