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.lang.*;
import java.util.*;
import java.io.*;


public class CF1213C {
	public static void main(String[] args) throws IOException {
		Reader.init(System.in);
		int n = Reader.nextInt(), q = Reader.nextInt();
		// read input tree
		UFDS yeeter = new UFDS(n);
		Edge[] treeEdges = new Edge[n - 1];
		for (int i = 0; i < n - 1; ++i) {
			int u = Reader.nextInt(), v = Reader.nextInt(), w = Reader.nextInt();
			--u; --v;
			treeEdges[i] = new Edge(u, v, w);
		}
		Arrays.sort(treeEdges);
		TreeMap<Integer, Long> precomp = new TreeMap<Integer, Long>();
		// precompute queries for n - 1 edges
		for (int i = 0; i < n - 1; ++i) {
			yeeter.join(treeEdges[i].x, treeEdges[i].y);
			precomp.put(treeEdges[i].w, yeeter.countConnPairs());
		}
		// answer queries
		for (int qta = 0; qta < q; ++qta) {
			int w = Reader.nextInt();
			Map.Entry<Integer, Long> bestWeight = precomp.floorEntry(w);
			if (bestWeight == null) {
				System.out.printf("0");
			} else {
				System.out.printf("%d", bestWeight.getValue());	
			}
			if (qta < q - 1) System.out.printf(" ");
		}
		System.out.printf("\n");
	}
};
interface UFDSer {
	public long countConnPairs();
	public int find(int i);
	public void join(int i, int j);
};

class UFDS implements UFDSer {
	public long connPairs;
	public long countConnPairs() {
		return connPairs;
	}
	private int[] par;
	public UFDS(int n) {
		par = new int[n];
		for (int i = 0; i < n; ++i) par[i] = -1;
		connPairs = 0;
	}
	public int find(int i) {
		if (par[i] < 0) return i;
		int ans = find(par[i]);
		par[i] = ans;
		return ans;
	}
	public void join(int i, int j) {
		i = find(i); j = find(j);
		if (i == j) return;
		int head = i, tail = j;
		if (par[head] > par[tail]) {
			head = j; tail = i;
		}
		connPairs += (long)par[head] * par[tail];
		par[head] += par[tail];
		par[tail] = head;
	}
};

class Reader {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	/** call this method to initialize reader for InputStream */
	static void init(InputStream input) {
		reader = new BufferedReader(
					new InputStreamReader(input) );
		tokenizer = new StringTokenizer("");
	}

	/** get next word */
	static String next() throws IOException {
		while ( ! tokenizer.hasMoreTokens() ) {
			//TODO add check for eof if necessary
			tokenizer = new StringTokenizer(
				reader.readLine() );
		}
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt( next() );
	}
	static long nextLong() throws IOException {
		return Long.parseLong( next() );
	}
	static double nextDouble() throws IOException {
		return Double.parseDouble( next() );
	}
}

class Edge implements Comparable<Edge> {
	public int x;
	public int y;
	public int w;
	public Edge(int x, int y, int w) {
		this.x = x;
		this.y = y;
		this.w = w;
	}
	public int compareTo(Edge other) {
		if (w != other.w) return w < other.w ? -1 : 1;
		else return 0;
	}
}