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:


/*
TASK: template
LANG: JAVA
 */
import java.io.*;
import java.lang.*;
import java.lang.reflect.Array;
import java.util.*;

public class G1213 {
    static int[] dsu;
    static int[] size;
    public static void main(String[] args) throws IOException{
        StringBuffer ans = new StringBuffer();
        StringTokenizer st;
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        dsu = new int[n+1];
        size = new int[n+1];
        Arrays.fill(size,1);
        for(int i = 0; i < n; i++) dsu[i] = i;
        PriorityQueue<point> pq = new PriorityQueue<>();
        for(int i = 0; i < n-1; i++){
            st = new StringTokenizer(f.readLine());
            pq.add(new point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        Integer[] arr = new Integer[m];
        st = new StringTokenizer(f.readLine());
        for(int x = 0; x < m; x++){
            arr[x] = Integer.parseInt(st.nextToken());
        }
        Integer[] arr1 = arr.clone();
        Arrays.sort(arr);
        HashMap<Integer, Long> hash = new HashMap<>();
        f.close();
        long curr = 0;
        for(int i : arr){
            while (!pq.isEmpty() && pq.peek().r <= i){
                int ft = pq.peek().x;
                int sc = pq.poll().y;
                long r1 = size[find(ft)];
                long r2 = size[find(sc)];
                curr-=(r1*(r1-1))/2;
                curr-=(r2*(r2-1))/2;
                r1+=r2;
                curr+=(r1*(r1-1))/2;
                union(ft,sc);
            }
            hash.put(i, curr);
        }

        for(int i : arr1)
            ans.append(hash.get(i)).append(" ");

        System.out.println(ans);

    }
    public static int find(int node){
        if(dsu[node] == node) return node;
        int r = find(dsu[node]);
        dsu[node] = r;
        return r;
    }
    public static void union(int ft, int sc){
        int a = find(ft);
        int b = find(sc);
        if(a != b) {
            if (size[a] < size[b]) {
                int temp = a;
                a = b;
                b = temp;
            }
            dsu[b] = a;
            size[a]+=size[b];
        }
    }
    public static class point implements Comparable<point>{
        int x;
        int y;
        int r;
        public point(int x,int y, int r){
            this.x = x;
            this.y = y;
            this.r = r;

        }
        public String toString(){
            return(x + " " + y);
        }
        public boolean equals(Object x){
            point y = ((point)(x));
            if (this.x == y.x && this.y == y.y){
                return true;
            }
            return false;
        }
        public int hashCode(){
            return Objects.hash(x,y);
        }
        public int compareTo(point other){
            if(this.r > other.r){
                return 1;
            }else if(this.r == other.r){
                return 0;
            }
            return -1;
        }
    }
}