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

    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int m = in.nextInt();
        node[] nodes = new node[n];

        for (int i = 0; i < n; i++) {
            nodes[i] = new node();
            nodes[i].set = i;

        }
        edge[] edges = new edge[n - 1];
//        PriorityQueue<edge> pq=new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));


        int maxW = 0;
        for (int i = 0; i < n - 1; i++) {
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            int weight = in.nextInt();
            if (weight > maxW) {
                maxW = weight;
            }
            edges[i] = new edge(nodes[x], nodes[y], weight);
            //          pq.add(edges[i]);
    //        nodes[x].arr.add(edges[i]);
    //        nodes[y].arr.add(edges[i]);
        }

        Arrays.sort(edges, Comparator.comparingInt(o -> o.weight));
//        for (int i = 0; i < edges.length; i++) {
//            System.out.println(edges[i].weight);
//        }

        int[] query = new int[m];
        for (int i = 0; i < m; i++) {
            query[i] = in.nextInt();
        }

        long[] ans = new long[maxW + 1];
        long temp = 0;
        int p = 1;

        for (int o = 0; o < edges.length; o++) {
            edge t = edges[o];
            int w = t.weight;
            while (w != p) {
                ans[p] = temp;
                p++;
            }

            node x = t.n1;
            node y = t.n2;
            temp += x.top().cnt * y.top().cnt;
            if (x.top().height > y.top().height) {
                x.top().cnt += y.top().cnt;
                y.top().father = x.top();
            } else {
                y.top().cnt += x.top().cnt;
                x.top().father = y.top();
                if (x.top().height == y.top().height) y.height++;
            }
            ans[p] = temp;

            if (o + 1 < edges.length && edges[o + 1].weight != w) {
                p++;
            }

        }


//            while(!pq.isEmpty()){
//
//                edge t=pq.peek();
//                int w=t.weight;
//                if(w!=p) {
//           //         pq.poll();
//                    ans[p]=temp;
//                    p++;
//                }
//                else {
//                    while(!pq.isEmpty()&&pq.peek().weight==p){
//                        t=pq.poll();
//                        node x=t.n1;
//                        node y=t.n2;
//                        temp+=x.top().cnt*y.top().cnt;
//        //                temp+=(long)sets[x.set].arr.size()*(long)sets[y.set].arr.size();
//
//                        if(x.top().height>y.top().height){
//                            x.top().cnt+=y.top().cnt;
//                            y.top().father=x.top();
//                        }else {
//                            y.top().cnt+=x.top().cnt;
//                            x.top().father=y.top();
//                            if(x.top().height==y.top().height)y.height++;
//                        }
//                    }
//                    ans[p]+=temp;
//                    p++;
//                }
//            }


//        for (int i = 0; i <maxW+1 ; i++) {
//            out.println(ans[i]);
//        }
        for (int i = 0; i < query.length; i++) {
            if (i != query.length - 1) {
                if (query[i] > maxW) out.print(ans[maxW] + " ");
                else out.print(ans[query[i]] + " ");
            } else {
                if (query[i] > maxW) out.print(ans[maxW]);
                else out.println(ans[query[i]]);
            }
        }

        out.close();
    }


    static class node {
        node father;
  //      ArrayList<edge> arr;
        int set = 0;
        long cnt = 1;
        int height = 1;

        public node() {
   //         arr = new ArrayList<>();
            father = this;
        }

        node top() {
            node t = this;
            while (t.father != t) {
                t = t.father;
            }
            return t;
        }
    }

    static class edge {
        int weight;
        node n1;
        node n2;

        public edge(node n1, node n2, int weight) {
            this.n1 = n1;
            this.n2 = n2;
            this.weight = weight;
        }


    }


    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, cnt);
        }

        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();
        }
    }

}