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 final class code
// public class Main
// class code
// public class Solution
{
    static void solve()throws IOException
    {
        int n=nextInt();
        int m=nextInt();
        ArrayList<Triplet> list=new ArrayList<Triplet>();
        for(int i=1;i<n;i++){
            int u=nextInt();
            int v=nextInt();
            int w=nextInt();
            list.add(new Triplet(u,v,w));
        }
        Collections.sort(list,new Comparator<Triplet>(){
            public int compare(Triplet a,Triplet b){
                return a.third-b.third;
            }
        });
        // debug(list);
        parent=new int[n+1];
        rank=new int[n+1];
        size=new int[n+1];
        for(int i=1;i<=n;i++)
        {
            parent[i]=i;
            size[i]=1;
        }
        ArrayList<Pair> queries=new ArrayList<>();
        queries.add(null);
        for(int i=1;i<=m;i++)
            queries.add(new Pair(nextInt(),i));
        Collections.sort(queries.subList(1,m+1),new Comparator<Pair>(){
            public int compare(Pair a,Pair b){
                return a.first-b.first;
            }
        });
        long ans[]=new long[m+1];
        int c=0;
        long res=0;
        for(int i=1;i<=m;i++){
            while(c<=n-2 && queries.get(i).first>=list.get(c).third){
                Triplet e=list.get(c++);
                res+=1l*size[find(e.first)]*size[find(e.second)];
                // debug("res",res);
                union(e.first,e.second);
                // debug("size",size[find(e.first)]);
            }
            ans[queries.get(i).second]=res;
        }
        for(int i=1;i<=m;i++)
            out.print(ans[i]+" ");
    }
    static class Pair
    {
        int first,second;
        Pair(int a,int b)
        {
            first=a;
            second=b;
        }
        public boolean equals(Object o)
        {
            if(o==null)
                return false;
            Pair p=(Pair)o;
            return first==p.first?second==p.second:false;
        }
        public int hashCode()
        {
            return (int)((1l*first*inf+second)%mod);
        }
        public String toString()
        {
            return first+" "+second;
        }
    }
    static class Triplet
    {
        int first,second,third;
        Triplet(int a,int b,int c)
        {
            first=a;
            second=b;
            third=c;
        }
        public boolean equals(Object o)
        {
            if(o==null)
                return false;
            Triplet p=(Triplet)o;
            if(first==p.first && second==p.second && third==p.third)
                return true;
            return false;
        }
        public int hashCode()
        {
            long x=(1l*first*inf+second)%mod;
            x=(x*inf+third)%mod;
            return (int)x;
        }
        public String toString()
        {
            return first+" "+second+" "+third;
        }
    }
    static int parent[],rank[],size[];
    static int find(int a)
    {
        if(parent[a]==a)
            return a;
        parent[a]=find(parent[a]);
        return parent[a];
    }
    static void union(int a,int b)
    {
        a=find(a);
        b=find(b);
        int size_a=size[a];
        int size_b=size[b];
        if(a==b)
            return;
        if(rank[a]>rank[b])
            parent[b]=a;
        else if(rank[a]<rank[b])
            parent[a]=b;
        else
        {
            rank[b]++;
            parent[a]=b;
        }
        size[find(a)]=size_a+size_b;
    }

     
    ///////////////////////////////////////////////////////////

    static final long mod=(long)(1e9+7);
    static final int inf=(int)(1e9+1);
    static final int maxn=(int)(1e6);
    static final long lim=(long)(1e18);

    public static void main(String args[])throws IOException
    {
        br=new BufferedReader(new InputStreamReader(System.in));
        out=new PrintWriter(new BufferedOutputStream(System.out));
        
        solve();
         
        // int t=nextInt();
        // for(int i=1;i<=t;i++)
        // {
        //    // out.print("Case #"+i+": ");
        //     solve();
        // }
         
        out.close();
    }
    
    static int max(int ... a)
    {
    int ret=a[0];
    for(int i=1;i<a.length;i++)
    ret=Math.max(ret,a[i]);
    return ret;
    }
    static int min(int ... a)
    {
    int ret=a[0];
    for(int i=1;i<a.length;i++)
    ret=Math.min(ret,a[i]);
    return ret;
    }
    static void debug(Object ... a)
    {
    System.out.print("> ");
    for(int i=0;i<a.length;i++)
    System.out.print(a[i]+" ");
    System.out.println();
    }
    static void debug(int a[]){debuga(Arrays.stream(a).boxed().toArray());}
    static void debug(long a[]){debuga(Arrays.stream(a).boxed().toArray());}
    static void debuga(Object a[])
    {
    System.out.print("> ");
    for(int i=0;i<a.length;i++)
    System.out.print(a[i]+" ");
    System.out.println();
    }
    static Random random;
    static BufferedReader br;
    static StringTokenizer st;
    static PrintWriter out;
    static String nextToken()throws IOException
    {
    while(st==null || !st.hasMoreTokens())
    st=new StringTokenizer(br.readLine());
    return st.nextToken();
    }
    static String nextLine()throws IOException
    {
    return br.readLine();
    }
    static int nextInt()throws IOException
    {
    return Integer.parseInt(nextToken());
    }
    static long nextLong()throws IOException
    {
    return Long.parseLong(nextToken());
    }
    static double nextDouble()throws IOException
    {
    return Double.parseDouble(nextToken());
    }
}