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:
// package CodeForces;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.LinkedList;

public class Round595F {

	public static int[][] dp; // dp[i][j] --> ith node with distance j selected node
	public static LinkedList<Integer>[] adj;
	public static int[] value;
	public static int K, n;
	
	public static void dfs(int current, int pr) {
		for(Integer x : adj[current]) {
			if(x != pr) {
				dfs(x, current);
			}
		}
		dp[current] = new int[K + 1];
		// when I'm selected as one of the node for subset
		dp[current][0] = value[current];
		for(Integer x : adj[current]) {
			if(x != pr) {
				dp[current][0] += dp[x][K];
			}
		}
		// when I'm not selected as one of the node for subset
		for(int i = 1; i <= K; i++) {
			int left = K - i;
			if(left >= i) {
				// one distance with i and all other with left
				int sum = 0;
				for(Integer x : adj[current]) {
					if(x != pr) {
						sum += dp[x][left];
					}
				}
				int max = 0;
				for(Integer x : adj[current]) {
					if(x != pr) {
						max = Integer.max(max, sum - dp[x][left] + dp[x][i - 1]);
					}
				}
				dp[current][i] = max;
			}else {
				// all distances are same
				for(Integer x : adj[current]) {
					if(x != pr) {
						dp[current][i] += dp[x][i - 1];
					}
				}
			}
		}
		// do suffix maximum of the dp array
		for(int i = K - 1; i >= 0; i--) {
			dp[current][i] = Integer.max(dp[current][i + 1], dp[current][i]);
		}
	}
	
	public static void solve() {
		n = s.nextInt();
		K = s.nextInt();
		value = s.nextIntArray(n);
		adj = new LinkedList[n];
		for(int i = 0; i < n; i++) {
			adj[i] = new LinkedList<Integer>();
		}
		for(int i = 0; i < n - 1; i++) {
			int u = s.nextInt() - 1;
			int v = s.nextInt() - 1;
			adj[u].add(v);
			adj[v].add(u);
		}
		dp = new int[n][];
		dfs(0, 0);
		out.println(dp[0][0]);
	}

	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 27) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					s = new FastReader(System.in);
					solve();
					out.close();
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}

	public static PrintWriter out;
	public static FastReader s;

	public static class FastReader {

		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;

		public FastReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (snumChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException E) {
					throw new InputMismatchException();
				}
			}
			if (snumChars <= 0) {
				return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndofLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}

	
}