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

public class PathQueries {

	// https://codeforces.com/gym/335765/problem/B
	
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader in = new BufferedReader(new FileReader("PathQueries"));

		StringTokenizer st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		A[] arr = new A[n-1];
		for (int i=0; i<n-1; i++ ) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken());
			arr[i] = new A(a,b,c);
		}
		Arrays.parallelSort(arr);
		DSU dsu = new DSU(n);
		
		st = new StringTokenizer(in.readLine());
		B[] queries = new B[m];
		for (int i=0; i<m; i++) {
			queries[i] = new B(Integer.parseInt(st.nextToken()), i);
		}
		Arrays.parallelSort(queries);
		
		StringBuilder s = new StringBuilder();
		long[] answers = new long[m];
		long ans = 0;
		int p = 0;
		for (int i=0; i<m; i++) {
			while (p < n-1 && arr[p].w <= queries[i].a) {
				int parent1 = dsu.FindSet(arr[p].a);
				int parent2 = dsu.FindSet(arr[p].b);
				ans -= choose(dsu.size[parent1]);
				ans -= choose(dsu.size[parent2]);
				dsu.Union(parent1, parent2);
				ans += choose(dsu.size[dsu.FindSet(parent1)]);
				++p;
			}
			answers[queries[i].i] = ans;
		}
		
		for (int i=0; i<m; i++) s.append(answers[i] + " ");
		
		System.out.println(s);
	}
	
	public static long choose(int x) {
		return (long)(x) * (x-1)/2;
	}
	
	static class A implements Comparable<A> {
		int a, b, w;
		A (int a, int b, int w) {
			this.a = a;
			this.b = b;
			this.w = w;
		}
		public int compareTo(A o) {
			return w - o.w;
		}
	}
	
	static class B implements Comparable<B> {
		int a, i;
		B (int a, int i) {
			this.a = a;
			this.i = i;
		}
		public int compareTo(B o) {
			return a - o.a;
		}
	}
	
	static class DSU {
		int n;
		int[] parent;
		int[] size;
		
		DSU (int n) {
			this.n = n;
			parent = new int[n];
			size = new int[n];
			for (int i=0; i<n; i++) {parent[i] = i; size[i] = 1;}
		}

		public int FindSet(int a) {
			if (a == parent[a]) return a;
			return parent[a] = FindSet(parent[a]);
		}
		
		public void Union(int a, int b) {
			a = FindSet(a);
			b = FindSet(b);
			if (a == b) return;
			
			if (size[a] < size[b]) {
				parent[a] = b;
				size[b] += size[a];
			}
			else {
				parent[b] = a;
				size[a] += size[b];
			}
		}
	}
}