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 G {

	public static Reader sc = new Reader();
	//public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static class dsu {
		int[] p;
		long[] ans;
		long result = 0;
		public dsu(int n) {
			p = new int[n];
			ans = new long[n];
			for (int i = 0; i < n; i++) {
				p[i] = i;
				ans[i] = 1L;
			}
		}
		int find(int a) {
			if (a == p[a]) return a;
			p[a] = find(p[a]);
			return p[a];
		}
		
		void merge(int a, int b) {
			result -= (eval(ans[find(a)]) + eval(ans[find(b)]));
			ans[find(b)] += ans[find(a)];
			p[find(a)] = p[find(b)];
			//System.out.println("The answer is: " + ans[b]);
			result += eval(ans[find(b)]);
		}
		public long eval(long a) {
			return a * (a-1)/2;
		}
		boolean check(int a, int b) {return p[a] == p[b];}
	}
	static class Edge implements Comparable<Edge>{
		public int a, b, w;
		public Edge(int x, int y, int z) {
			a=x;
			b=y;
			if (a < b) {
				x^=y;
				y^=x;
				x^=y;
			}
			w=z;
		}
		public int compareTo(Edge o) {
			return w - o.w;
		}
	}
	static class Query implements Comparable<Query>{
		public int i, w;
		public Query(int x, int y) {
			i=x;
			w=y;
		}
		public int compareTo(Query o) {
			return w - o.w;
		}
	}
	public static void main(String[] args) throws IOException {
		//BufferedReader br = new BufferedReader(new FileReader("input.in"));

		int n = sc.nextInt();
		int m = sc.nextInt();
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		dsu d =  new dsu(n);
		for (int i = 0; i < n-1; i++) {
			pq.add(new Edge(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt()));
		}
		long[] sol = new long[m];
		Query[] q = new Query[m];
		for (int i = 0; i < m; i++) {
			q[i] = new Query(i, sc.nextInt());
		}
		Arrays.sort(q);
		for (int i = 0; i < m; i++) {
			//System.out.println("New venture: " + i);
			while (!pq.isEmpty() && pq.peek().w <= q[i].w) {
				Edge e = pq.poll();
				d.merge(e.a, e.b);
			}
			sol[q[i].i] = d.result;
		}
		for (long x: sol) out.print(x + " ");
		out.println();
		out.close();
	}

	static long ceil(long a, long b) {
		return (a + b - 1) / b;
	}

	static long powMod(long base, long exp, long mod) {
		if (base == 0 || base == 1)
			return base;
		if (exp == 0)
			return 1;
		if (exp == 1)
			return base % mod;
		long R = powMod(base, exp / 2, mod) % mod;
		R *= R;
		R %= mod;
		if ((exp & 1) == 1) {
			return base * R % mod;
		} else
			return R % mod;
	}

	static long pow(long base, long exp) {
		if (base == 0 || base == 1)
			return base;
		if (exp == 0)
			return 1;
		if (exp == 1)
			return base;
		long R = pow(base, exp / 2);
		if ((exp & 1) == 1) {
			return R * R * base;
		} else
			return R * R;
	}

	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length 
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n') {
					break;
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, Integer.max(cnt - 1, 0));
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
}