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 {
    public static void main(String args[])
    {
        FastReader input=new FastReader();
        PrintWriter out=new PrintWriter(System.out);
        int T=1;
        while(T-->0)
        {
            int n=input.nextInt();
            int m=input.nextInt();
            int index[]=new int[n+1];
            int visit[]=new int[n+1];
            ArrayList<HashSet<Integer>> list=new ArrayList<>();
            ArrayList<Pair> weights[]=new ArrayList[200001];
            for(int i=0;i<n-1;i++)
            {
                int u=input.nextInt();
                int v=input.nextInt();
                int w=input.nextInt();
                if(weights[w]==null)
                {
                    weights[w]=new ArrayList<>();
                }
                weights[w].add(new Pair(u,v));
            }
            long sum=0;
            long ans[]=new long[200001];
            for(int i=1;i<=200000;i++)
            {
                if(weights[i]!=null)
                {
                    for(int j=0;j<weights[i].size();j++)
                    {
                        int u=weights[i].get(j).u;
                        int v=weights[i].get(j).v;
                        if(visit[u]==1 && visit[v]==0)
                        {
                            int ind=index[u];
                            int size=list.get(ind).size();
                            sum-=(long)size*(long)(size-1)/2;
                            sum+=(long)(size)*(long)(size+1)/2;
                            list.get(ind).add(v);
                            index[v]=ind;
                            visit[v]=1;
                        }
                        else if(visit[u]==0 && visit[v]==1)
                        {
                            int ind=index[v];
                            int size=list.get(ind).size();
                            sum-=(long)size*(long)(size-1)/2;
                            sum+=(long)(size)*(long)(size+1)/2;
                            list.get(ind).add(u);
                            index[u]=ind;
                            visit[u]=1;
                        }
                        else if(visit[u]==1 && visit[v]==1)
                        {
                            int ind1=index[u];
                            int ind2=index[v];
                            if(ind1!=ind2)
                            {
                                int size1=list.get(ind1).size();
                                int size2=list.get(ind2).size();
                                sum-=(long)size1*(long)(size1-1)/2;
                                sum-=(long)size2*(long)(size2-1)/2;
                                sum+=(long)(size1+size2)*(long)(size1+size2-1)/2;
                                if(size2<=size1)
                                {
                                    Iterator it=list.get(ind2).iterator();
                                    while(it.hasNext())
                                    {
                                        int nu=(int)it.next();
                                        list.get(ind1).add(nu);
                                        index[nu]=ind1;
                                    }
                                }
                                else
                                {
                                    Iterator it=list.get(ind1).iterator();
                                    while(it.hasNext())
                                    {
                                        int nu=(int)it.next();
                                        list.get(ind2).add(nu);
                                        index[nu]=ind2;
                                    }
                                }
                            }
                        }
                        else
                        {
                            HashSet<Integer> set=new HashSet<>();
                            set.add(u);
                            set.add(v);
                            list.add(set);
                            index[u]=list.size()-1;
                            index[v]=list.size()-1;
                            visit[u]=1;
                            visit[v]=1;
                            sum+=1;
                        }
                    }
                    ans[i]=sum;
                }
                else
                {
                    ans[i]=sum;
                }
            }
            for(int i=0;i<m;i++)
            {
                int q=input.nextInt();
                out.print(ans[q]+" ");
            }
            out.println();
        }
        out.close();
    }
    static class Pair
    {
        int u,v;
        Pair(int u,int v)
        {
            this.u=u;
            this.v=v;
        }
    }
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
        public FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt()
        {
            return Integer.parseInt(next());
        }
        long nextLong()
        {
            return Long.parseLong(next());
        }
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}