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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;



public class TaskG {
        public static void main(String[] args) throws Exception {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st;
                PrintWriter pw = new PrintWriter(System.out);

                st = new StringTokenizer(br.readLine());
                int n = Integer.parseInt(st.nextToken());
                int m = Integer.parseInt(st.nextToken());

                Edge[] edge = new Edge[n-1];

                PriorityQueue<Edge> pq = new PriorityQueue<>(10, new Comparator<Edge>() {
                        @Override
                        public int compare(Edge o1, Edge o2) {
                                return o1.w-o2.w;
                        }
                });

                for(int i=0 ; i<n-1 ; i++) {
                        st = new StringTokenizer(br.readLine());
                        int u = Integer.parseInt(st.nextToken());
                        int v = Integer.parseInt(st.nextToken());
                        int w = Integer.parseInt(st.nextToken());
                        edge[i] = new Edge(u,v,w);
                        pq.add(edge[i]);
                }

                Pair[] queries  = new Pair[m];
                st = new StringTokenizer(br.readLine());
                for(int i=0 ; i<m ; i++) {
                        queries[i] = new Pair(Integer.parseInt(st.nextToken()), i);
                }

                Arrays.sort(queries, new Comparator<Pair>() {
                        @Override
                        public int compare(Pair o1, Pair o2) {
                                return o1.x-o2.x;
                        }
                });

                DSU dsu = new DSU(n+1);

                long sum = 0;
                for(int i=0 ; i<m ; i++) {
                        int x = queries[i].x;
                        if(pq.isEmpty()) {
                                queries[i].ans = ncr(n,2);
                        }
                        else {
                                while(!pq.isEmpty() && pq.peek().w <= x) {
                                        Edge e = pq.poll();
                                        int s1 = dsu.getSize(dsu.find(e.u));
                                        int s2 = dsu.getSize(dsu.find(e.v));
                                        sum -= ncr(s1, 2);
                                        sum -= ncr(s2, 2);
                                        int size = dsu.union(e.u, e.v);
                                        sum += ncr(size, 2);
                                }
                        }

                        queries[i].ans = sum;
                }

                Arrays.sort(queries, new Comparator<Pair>() {
                        @Override
                        public int compare(Pair o1, Pair o2) {
                                return o1.y-o2.y;
                        }
                });

                for(int i=0 ; i<m ; i++) {
                        pw.print(queries[i].ans + " ");
                }

                pw.flush();
                pw.close();
        }

        static long ncr(int n, int r) {
                if(n<r) {
                        return 0;
                }
                if(r > n-r) {
                        r = n-r;
                }
                long num = 1;
                long den = 1;
                for(int i=1 ; i<=r ; i++) {
                        num *= n-i+1;
                        den *= i;

                        long temp = gcd(num , den);
                        num /= temp;
                        den /= temp;
                }

                return num/den;
        }

        static long gcd(long a, long b) {
                return b==0?a:gcd(b,a%b);
        }
}

class Pair {
        int x;
        int y;
        long ans;
        Pair(int u, int v) {
                x = u;
                y = v;
        }
}

class Edge {
        int u;
        int v;
        int w;
        Edge(int a, int b, int c) {
                u = a;
                v = b;
                w = c;
        }
}

class DSU {
        int n;
        int[] parent;
        int[] size;

        DSU(int v) {
                n = v;
                parent = new int[n];
                size = new int[n];
                for(int i=0 ; i<n ; i++) {
                        parent[i] = i;
                        size[i] = 1;
                }
        }

        int find(int a) {
                int root = a;

                while(parent[root] != root) {
                        root = parent[root];
                }

                while(a != root) {
                        int temp = parent[a];
                        parent[a] = root;
                        a = temp;
                }

                return root;
        }

        int getSize(int a) {
                return size[a];
        }

        int union(int u, int v) {
                int root_u = find(u);
                int root_v = find(v);

                if(root_u == root_v) {
                        return size[root_u];
                }

                int size_u = size[root_u];
                int size_v = size[root_v];
                if(size_u > size_v) {
                        parent[root_v] = root_u;
                        size[root_u] += size_v;
                        return size[root_u];
                }
                else {
                        parent[root_u] = root_v;
                        size[root_v] += size_u;
                        return size[root_v];
                }
        }
}