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 Ishu
{
    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;
    int v;
    int w;
    int idx;
    Edge(int u, int v, int w, int idx)
        {
        this.u = u;
        this.v = v;
        this.w = w;
        this.idx = idx;
        }
    }
    static Reader scan = new Reader();
    static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out)); 
    static void tc() throws Exception
    {
    int n = scan.nextInt();
    int m = scan.nextInt();
    List<Edge> edge = new ArrayList<Edge>();
    int i;
    for(i=0;i<n-1;++i)
        {
        int u = scan.nextInt() - 1;
        int v = scan.nextInt() - 1;
        int w = scan.nextInt();
        int idx = i;
        edge.add(new Edge(u, v, w, idx));
        }
    
    Collections.sort(edge, new Comparator<Edge>(){
        public int compare(final Edge x, final Edge y)
            {
            return x.w - y.w;
            }
    });
    
    long ANS = 0L;
    
    long[] ans = new long[200001];
    int[] kid = new int[n];
    int[] leader = new int[n];
   
    Arrays.fill(kid, 1);
    for(i=0;i<n;++i)
        leader[i] = i;
        
    for(i=0;i<n-1;++i)
        {
        Edge cr = edge.get(i);
        int u = cr.u;
        int v = cr.v;
        int w = cr.w;
        
        int lu = leader[u];
        while(lu != leader[lu])
            lu = leader[lu];
            
        int lv = leader[v];
        while(lv != leader[lv])
            lv = leader[lv];
            
        int ku = kid[lu];
        int kv = kid[lv];
        
        ANS += 1L * ku * kv;
        
        if(ku <= kv)
            {
            int nkv = kv + ku;
            leader[lu] = lv;
            kid[lv] = nkv;
            }
        else
            {
            int nku = kv + ku;
            leader[lv] = lu;
            kid[lu] = nku;
            }
            
        ans[w] = ANS;
        } 
    long prev = ans[0];
    for(i=1;i<=200000;++i)  
        {
        if(ans[i] == 0)
            ans[i] = prev;
          
        prev = ans[i];
        }
    
    while(m-- > 0)
        {
        int q = scan.nextInt();
        output.write(ans[q] + " ");
        }
    output.write("\n");
    output.flush();
    }
    public static void main(String[] args) throws Exception
    {
    int t = 1;
    //t = scan.nextInt();
    while(t-- > 0)
        tc();
    }
}