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

public class CF1213G extends PrintWriter {
	CF1213G() { super(System.out); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		int k, l; byte[] bb = new byte[1 << 15];
		byte getc() {
			if (k >= l) {
				k = 0;
				try { l = in.read(bb); } catch (IOException e) { l = 0; }
				if (l <= 0) return -1;
			}
			return bb[k++];
		}
		int nextInt() {
			byte c = 0; while (c <= 32) c = getc();
			int a = 0;
			while (c > 32) { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1213G o = new CF1213G(); o.main(); o.flush();
	}

	int[] dsu;
	int find(int i) {
		return dsu[i] < 0 ? i : (dsu[i] = find(dsu[i]));
	}
	long join(int i, int j) {
		i = find(i);
		j = find(j);
		if (i == j)
			return 0;
		long p = (long) dsu[i] * dsu[j];
		if (dsu[i] > dsu[j]) {
			int tmp = i; i = j; j = tmp;
		}
		dsu[i] += dsu[j];
		dsu[j] = i;
		return p;
	}
	void main() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		dsu = new int[n]; Arrays.fill(dsu, -1);
		int[] ii = new int[n - 1];
		int[] jj = new int[n - 1];
		int[] ww = new int[n - 1];
		Integer[] hh = new Integer[n - 1];
		for (int h = 0; h < n - 1; h++) {
			ii[h] = sc.nextInt() - 1;
			jj[h] = sc.nextInt() - 1;
			ww[h] = sc.nextInt();
			hh[h] = h;
		}
		Arrays.sort(hh, (e, f) -> ww[e] - ww[f]);
		int[] qq = new int[m];
		long[] pp = new long[m];
		Integer[] gg = new Integer[m];
		for (int g = 0; g < m; g++) {
			qq[g] = sc.nextInt();
			gg[g] = g;
		}
		Arrays.sort(gg, (u, v) -> qq[u] - qq[v]);
		long p = 0;
		for (int h = 0, g = 0; g < m; g++) {
			int h_, g_ = gg[g];
			while (h < n - 1 && ww[h_ = hh[h]] <= qq[g_]) {
				p += join(ii[h_], jj[h_]);
				h++;
			}
			pp[g_] = p;
		}
		for (int g = 0; g < m; g++)
			print(pp[g] + " ");
		println();
	}
}