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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.stream.Collectors;


public class E{
	
	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; 
        } 
    }
	
	static class Pair
	{
		int f;
		int t;
		int w;
		Pair(int f,int t,int w)
		{
			this.f = f;
			this.t = t;
			this.w = w;
		}
		
	}
	
	static int find(int parent[], int rank[], int i) 
	{ 
	if (parent[i] != i) 
	    parent[i] = find(parent, rank, parent[i]); 
	    return parent[i]; 
	}
	
	static void Union(int parent[],int rank[],int sum[], int x , int y ) 
	{ 
	    int xroot = find(parent, rank, x); 
	        int yroot = find(parent, rank, y); 
	  
	    if (rank[xroot] < rank[yroot])
	    {
	        parent[xroot] = yroot; 
	        sum[yroot] += sum[xroot]; 
	    }
	    else if (rank[yroot] < rank[xroot]) 
	    {
	        parent[yroot] = xroot; 
	        sum[xroot] += sum[yroot]; 
	    }
	    else
	    { 
	        parent[xroot] = yroot; 
	        sum[yroot] += sum[xroot]; 
	        rank[yroot]++; 
	    } 
	}  
	public static void main(String[] args) 
	{
		OutputStream outputStream = System.out;
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int parent[] = new int[n+1];
        int rank[] = new int[n+1];
        int sum[] = new int[n+1];
        
        Arrays.fill(sum,1);
        long ans[] = new long[1000000];
        for(int i = 1; i <= n; i++) parent[i] = i;
        
        
        
        Pair pr[] = new Pair[n-1];
        
        for(int i = 0; i <n-1; i++)
        {
        	int f = sc.nextInt();
        	int t = sc.nextInt();
        	int w = sc.nextInt();
        	pr[i] = new Pair(f,t,w);
        }
        
        Arrays.sort(pr, (p,q)-> Integer.compare(p.w,q.w));
        
        long cans = 0L;
        for(int i = 0; i < pr.length; i++)
        {
        	int f = pr[i].f;
        	int t = pr[i].t;
        	int w = pr[i].w;
        	
        	int x = find(parent,rank,f);
        	int y = find(parent,rank,t);
        	
        	int v1 = sum[x];
        	int v2 = sum[y];
        	
        	long a1 = (long)((long)v1*(v1-1))/2;
        	long a2 = (long)((long)v2*(v2-1))/2;
        	
        	int v = v1+v2;
        	long a3 = (long)((long)v*(v-1))/2;
        	
        	cans += a3 - a1 - a2;
        	ans[w] = cans;
        	Union(parent,rank,sum,x,y);
        }
        
        for(int i = 1; i < ans.length; i++)
        {
        	if(ans[i] == 0)
        	{
        		ans[i] = ans[i-1];
        	}
        }
        
        for(int i = 0; i < m; i++)
        {
        	int x = sc.nextInt();
        	out.print(ans[x]+" ");
        }
        out.close();
	}

}