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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

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(); 
        } 
    } 
	
	public static void main(String[] args) throws Exception
	{
		Reader s=new Reader();
		
		StringBuilder sb=new StringBuilder();
		
		int n=s.nextInt();
		int m=s.nextInt();
		
		pair[] arr=new pair[n-1];
		
		for(int i=0;i<n-1;i++)
		{
			int a=s.nextInt();
			int b=s.nextInt();
			int w=s.nextInt();
			
			pair p=new pair(a,b,w);
			arr[i]=p;
		}
		
		Arrays.sort(arr,new comp());
		
		pair2[] query=new pair2[m];
		
		for(int i=0;i<m;i++)
		{
			int val=s.nextInt();
			
			pair2 p=new pair2(val,i);
			query[i]=p
					;
		}
		
		Arrays.sort(query,new comp2());
		
		int[] parent=new int[n+1];
		long[] count=new long[n+1];
		
		for(int i=0;i<n+1;i++)
		{
			parent[i]=i;
		}
		
		Arrays.fill(count,1);
		
		long[] answer=new long[m];
		
		int ptr=0;
		
		long ans=0;
		
		for(int i=0;i<m;i++)
		{
			int max=query[i].val;
			
			while(ptr<n-1&&arr[ptr].w<=max)
			{
				int a=arr[ptr].a;
				int b=arr[ptr].b;
				
				int parenta=find(a,parent);
				int parentb=find(b,parent);
				
				if(count[parenta]<=count[parentb])
				{
					ans=ans-ncr(count[parenta])-ncr(count[parentb]);
					
					parent[parenta]=parentb;
					count[parentb]=count[parenta]+count[parentb];
					
					count[parenta]=0;
					
					ans=ans+ncr(count[parentb]);
				}
				else
				{
					ans=ans-ncr(count[parenta])-ncr(count[parentb]);
					
					parent[parentb]=parenta;
					count[parenta]=count[parentb]+count[parenta];
					
					count[parentb]=0;
					
					ans=ans+ncr(count[parenta]);
				}
				
				ptr++;
				
			}
			
			answer[query[i].index]=ans;
			
		}
		
		for(int i=0;i<m;i++)
		{
			sb.append(answer[i]);
			sb.append(" ");
		}
		
		System.out.println(sb);
		
	}
	
	public static long ncr(long a)
	{
		return (a*(a-1))/2;
	}
	
	public static int find(int curr,int[] parent)
	{
		if(parent[curr]==curr)
			return curr;
		
		int leader=find(parent[curr],parent);
		parent[curr]=leader;
		
		return leader;
	}
	
}

class pair
{
	int a;
	int b;
	int w;
	
	public pair(int a,int b,int w)
	{
		this.a=a;
		this.b=b;
		this.w=w;
	}
}

class pair2
{
	int val;
	int index;
	
	public pair2(int val,int index)
	{
		this.val=val;
		this.index=index;
	}
}

class comp implements Comparator<pair>
{
	public int compare(pair a,pair b)
	{
		return a.w-b.w;
	}
}

class comp2 implements Comparator<pair2>
{
	public int compare(pair2 a,pair2 b)
	{
		return a.val-b.val;
	}
}