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.util.*;
import java.io.*;
public class Main
{
    static class Reader 
    { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead; 
  
        public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
  
        public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9'); 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
  
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
  
            if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            } 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        } 
  
        private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        } 
  
        public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    } 
    static class Edge
    {
        int u,v,w;
        Edge(int u,int v,int w)
        {
            this.u=u;
            this.v=v;
            this.w=w;
        }
    }
    static class DSU
    {
        int n;
        int par[];
        long ans[];
        int rank[];
        DSU(int n)
        {
            this.n=n;
            rank=new int[n];
            par=new int[n];
            ans=new long[300000];
            for(int i=1;i<n;i++)
            par[i]=i;
            Arrays.fill(rank,1);
        }
        public int find(int u)
        {
            if(par[u]==u)
            return u;
            return par[u]=find(par[u]);
        }
        public void union(int x,int y,int vert)
        {
            x=find(x);
            y=find(y);
            if(rank[x]<rank[y])
            {
                par[x]=y;
                ans[vert]=ans[vert]+1L*rank[x]*rank[y];
                rank[y]+=rank[x];
                rank[x]=0;
            }
            else if(rank[x]>rank[y])
            {
                par[y]=x;
                ans[vert]=ans[vert]+1L*rank[x]*rank[y];
                rank[x]+=rank[y];
                rank[y]=0;
            }
            else
            {
                par[y]=x;
                ans[vert]+=1L*rank[x]*rank[y];
                rank[x]+=rank[y];
                rank[y]=0;
            }
        }
    }
    public static void main(String args[])throws Exception
    {
        Reader sc=new Reader();
        PrintWriter pw=new PrintWriter(System.out);
        int n=sc.nextInt();
        int m=sc.nextInt();
        Edge[] e=new Edge[n-1];
        for(int i=0;i<n-1;i++)
        {
            int u=sc.nextInt();
            int v=sc.nextInt();
            int w=sc.nextInt();
            if(u>v)
            {
                int temp=u;
                u=v;
                v=temp;
            }
            e[i]=new Edge(u,v,w);
        }
        int q[]=new int[m];
        for(int i=0;i<m;i++)
        q[i]=sc.nextInt();
        Arrays.sort(e,(e1,e2)->e1.w-e2.w);
        DSU d=new DSU(n+1);
        for(int i=0;i<n-1;i++)
        d.union(e[i].u,e[i].v,e[i].w);
        for(int i=1;i<=200000;i++)
        d.ans[i]+=d.ans[i-1];
        for(int i=0;i<m;i++)
        pw.print(d.ans[q[i]]+" ");
        pw.flush();
        pw.close();
    }
}