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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Comparator;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Puneet    //FastRead class is taken from different online Sources
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastInput in = new FastInput(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskG solver = new TaskG();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskG {
        int[] parr = new int[1000001];
        long[] rank = new long[1000001];
        long ans = 0;

        void setParr() {
            for (int i = 0; i < 1000001; ++i) {
                parr[i] = i;
                rank[i] = 1L;
            }
        }

        int getParent(int u) {
            if (parr[u] == u)
                return u;
            return parr[u] = getParent(parr[u]);
        }

        void merge(int u, int v) {

            u = getParent(u);
            v = getParent(v);

            if (rank[u] < rank[v]) {
                u = u ^ v;
                v = u ^ v;
                u = u ^ v;
            }

            ans -= (rank[u] * (rank[u] - 1L)) / 2L;
            ans -= (rank[v] * (rank[v] - 1L)) / 2L;

            rank[u] += rank[v];

            ans += (rank[u] * (rank[u] - 1L)) / 2L;

            parr[v] = u;


        }

        public void solve(int testNumber, FastInput in, PrintWriter out) {

            setParr();
            int n = in.ni(), m = in.ni();
            ArrayList<Pair> list = new ArrayList<>();
            for (int i = 0; i < n - 1; ++i) {
                list.add(new Pair(in.ni(), in.ni(), in.ni()));
            }

            list.sort(new Comparator<Pair>() {
                public int compare(Pair p1, Pair p2) {
                    return p1.c - p2.c;
                }
            });

            ArrayList<Pair> query = new ArrayList<>();

            for (int i = 0; i < m; ++i) {
                query.add(new Pair(in.ni(), i, 0));
            }

            query.sort(new Comparator<Pair>() {

                public int compare(Pair pair, Pair t1) {
                    return pair.a - t1.a;
                }
            });

            int idx = 0;

            long[] fans = new long[m];

            for (int i = 0; i < m; ++i) {
                while (idx < n - 1 && query.get(i).a >= list.get(idx).c) {
                    merge(list.get(idx).a, list.get(idx).b);
                    ++idx;
//                out.println(idx);
                }

//            out.println(query.get(i).b+" "+ans+" -- "+idx);

                fans[query.get(i).b] = ans;
            }

            for (int i = 0; i < m; i++) {
                out.print(fans[i] + " ");
            }

            out.println();
        }

        class Pair {
            int a;
            int b;
            int c;

            public Pair(int a, int b, int c) {
                this.a = a;
                this.b = b;
                this.c = c;
            }

        }

    }

    static class FastInput {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastInput.SpaceCharFilter filter;

        public FastInput(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int ni() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}