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 {
	public static void main(String args[]) {new Main().run();}
	
	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
	    work();
	    out.flush();
	}
	long mod=998244353L;
	int[] id,count,weight;
	void work() {
		int n=in.nextInt();
		int m=in.nextInt();
		int[][] Q=new int[m][2];
		int[][] E=new int[n-1][3];
		for(int i=0;i<n-1;i++) {
			int s=in.nextInt()-1;
			int e=in.nextInt()-1;
			int w=in.nextInt();
			E[i][0]=w;
			E[i][1]=s;
			E[i][2]=e;
		}
		for(int i=0;i<m;i++) {
			Q[i][0]=in.nextInt();
			Q[i][1]=i;
		}
		long[] ret=new long[m];
		Arrays.sort(Q,new Comparator<int[]>() {
			public int compare(int[] A,int[] B) {
				return A[0]-B[0];
			}
		});
		Arrays.sort(E,new Comparator<int[]>() {
			public int compare(int[] A,int[] B) {
				return A[0]-B[0];
			}
		});
		id=new int[n];
		count=new int[n];
		weight=new int[n];
		for(int i=0;i<n;i++) id[i]=i;
		Arrays.fill(count, 1);
		
		long cnt=0;
		for(int i=0,j=0;i<m;i++) {
			int w=Q[i][0];
			int index=Q[i][1];
			while(j<n-1&&E[j][0]<=w) {
				int s=E[j][1];
				int e=E[j][2];
				int sroot=find(s);
				int eroot=find(e);
				cnt+=union(sroot,eroot);
				j++;
			}
			
			ret[index]=cnt;
		}
		
		for(int i=0;i<m;i++) {
			out.print(ret[i]+" ");
		}
	}
	
	
	int find(int n) {
		while(id[n]!=n) n=id[n];
		return n;
	}
	
	long union(int p,int q) {
		int proot=find(p);
		int qroot=find(q);
		long c1=count[proot],c2=count[qroot],c3=c1+c2;
		
		if(weight[proot]>weight[qroot]) {
			id[qroot]=proot;
			count[proot]+=count[qroot];
		}else if(weight[proot]<weight[qroot]) {
			id[proot]=qroot;
			count[qroot]+=count[proot];
		}else {
			id[qroot]=proot;
			weight[proot]++;
			count[proot]+=count[qroot];
		}
		
		return c3*(c3-1)/2-c2*(c2-1)/2-c1*(c1-1)/2;
	}
	
	
}
class FastReader
{
	BufferedReader br;
	StringTokenizer st;
 
	public FastReader()
	{
	    br=new BufferedReader(new InputStreamReader(System.in));
	}
 
	public String next() 
	{
	    if(st==null || !st.hasMoreElements())
	    {
	        try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
	    }
	    return st.nextToken();
	}
 
	public int nextInt() 
	{
	    return Integer.parseInt(next());
	}
 
	public long nextLong()
	{
	    return Long.parseLong(next());
	}
}