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.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.security.KeyStore.Entry;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	static Edge2 adj[];
	
	public static void main(String[] args) throws Exception {
		Scanner sc=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);
	int n=sc.nextInt();
	int m=sc.nextInt();
	int n1=n-1;
int i=0;
adj=new Edge2[n-1];
while(n1-->0) {
		adj[i]=new Edge2(sc.nextInt()-1, sc.nextInt()-1, sc.nextLong());
	i++;
	}
Arrays.sort(adj,(a,b)->Long.compare(a.cost,b.cost));

	UnionFind dsu=new UnionFind(n);
	Edge2 q[]=new Edge2[m];
	for (int j = 0; j < q.length; j++) {
		q[j]=new Edge2(j, 0, sc.nextLong());
	
	}
	int idx=0;
	long ans=0;
	long count=0;
	Arrays.sort(q,(a,b)->Long.compare(a.cost,b.cost));
	
	for (int j = 0; j < q.length; j++) {
		while(idx<n-1&&adj[idx].cost<=q[j].cost) {
			
			count+=(1l*(dsu.sizeOfSet(adj[idx].node))*1l*(dsu.sizeOfSet((int) adj[idx].next)*1l));
			dsu.unionSet(adj[idx].node, (int) adj[idx].next);
			
			
			idx++;
		}
		q[j].next=count;
	}
	Arrays.sort(q,(a,b)->Long.compare(a.node,b.node));
	
	for (long j = 0; j < q.length; j++) {
		System.out.println(q[(int) j].next);
	}
	
	
		out.flush();
	}	
	static class UnionFind {                                              
		int[] p, rank, setSize;
		int numSets;
 
		public UnionFind(int N) 
		{
			p = new int[numSets = N];
			rank = new int[N];
			setSize = new int[N];
			for (int i = 0; i < N; i++) {  p[i] = i; setSize[i] = 1; }
		}
 
		public int findSet(int i) { return p[i] == i ? i : (p[i] = findSet(p[i])); }
 
		public boolean isSameSet(int i, int j) { return findSet(i) == findSet(j); }
 
		public void unionSet(int i, int j) 
		{ 
			if (isSameSet(i, j)) 
				return;
			numSets--; 
			int x = findSet(i), y = findSet(j);
			if(rank[x] > rank[y]) { p[y] = x; setSize[x] += setSize[y]; }
			else
			{	p[x] = y; setSize[y] += setSize[x];
				if(rank[x] == rank[y]) rank[y]++; 
			} 
		}
		public int numDisjointSets() { return numSets; }
		 
		public int sizeOfSet(int i) { return setSize[findSet(i)]; }
	}
	public static int[] schuffle(int a[]) {
		for (int i = 0; i < a.length; i++) {
			int x=(int)(Math.random()*a.length);
		int temp=a[x];
		a[x]=a[i];
		a[i]=temp;
		}
		return a;
	}
		static int V;
	static int INF=(int) 1E9;
		
		static class Edge2 
		{
			int node;
		long cost;
			long next;
			Edge2(int a, int c,Long long1) { node = a;	cost = long1; next=c;}
			
		}
static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}	
}