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 CF1249F extends PrintWriter {
	CF1249F() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1249F o = new CF1249F(); o.main(); o.flush();
	}

	int[] oo, jj; int $ = 1;
	int link(int o, int j) {
		oo[$] = o; jj[$] = j;
		return $++;
	}
	int n, k;
	int[] ae, aa; int[][] ss; int[] tt;
	void init() {
		oo = new int[1 + (n - 1) * 2]; jj = new int[1 + (n - 1) * 2];
		ae = new int[n]; aa = new int[n];
		ss = new int[n][k + 1]; tt = new int[k];
	}
	void dfs(int p, int i) {
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = jj[o];
			if (j != p)
				dfs(i, j);
		}
		ss[i][0] += aa[i];
		Arrays.fill(tt, 0);
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = jj[o];
			if (j != p) {
				ss[i][0] += ss[j][k];
				for (int h = 0; h < k; h++)
					tt[h] += ss[j][h];
			}
		}
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = jj[o];
			if (j != p)
				for (int h = 0; h < k; h++) {
					// h + 1 + h_ + 1 >= k + 1
					int h_ = Math.max(h, k - h - 1);
					ss[i][h + 1] = Math.max(ss[i][h + 1], ss[j][h] + tt[h_] - ss[j][h_]);
				}
		}
		for (int h = k - 1; h >= 0; h--)
			ss[i][h] = Math.max(ss[i][h], ss[i][h + 1]);
	}
	void main() {
		n = sc.nextInt();
		k = sc.nextInt();
		init();
		for (int i = 0; i < n; i++)
			aa[i] = sc.nextInt();
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			ae[i] = link(ae[i], j);
			ae[j] = link(ae[j], i);
		}
		dfs(-1, 0);
		println(ss[0][0]);
	}
}