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.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Washoum
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        inputClass in = new inputClass(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        GPathQueries solver = new GPathQueries();
        solver.solve(1, in, out);
        out.close();
    }

    static class GPathQueries {
        static GPathQueries.Subset[] subsets;

        static int find(int i) {
            if (subsets[i].parent != i)
                subsets[i].parent = find(subsets[i].parent);
            return subsets[i].parent;
        }

        static void union(int x, int y) {
            int xroot = find(x);
            int yroot = find(y);

            if (subsets[xroot].size < subsets[yroot].size) {
                subsets[xroot].parent = yroot;
                subsets[yroot].size += subsets[xroot].size;
            } else {
                subsets[yroot].parent = xroot;
                subsets[xroot].size += subsets[yroot].size;
            }
        }

        public void solve(int testNumber, inputClass sc, PrintWriter out) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if (n == 1) {
                for (int i = 0; i < m; i++) {
                    out.print(0 + " ");
                }
                return;
            }
            subsets = new GPathQueries.Subset[n];
            for (int i = 0; i < n; i++) {
                subsets[i] = new GPathQueries.Subset();
                subsets[i].parent = i;
                subsets[i].size = 1;
            }
            GPathQueries.Edge[] edges = new GPathQueries.Edge[n - 1];
            for (int i = 0; i < n - 1; i++) {
                edges[i] = new GPathQueries.Edge(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
            }
            Arrays.sort(edges, Comparator.comparingInt(a -> a.w));
            int start = 0;
            int end = 0;
            long act = 0;
            ArrayList<GPathQueries.Pair> ans = new ArrayList<>();
            while (end < n - 1) {
                while (end < n - 1 && edges[start].w == edges[end].w) {
                    end++;
                }
                end--;
                for (int i = start; i <= end; i++) {
                    int a = find(edges[i].u);
                    int b = find(edges[i].v);
                    act -= ((long) subsets[a].size * (subsets[a].size - 1)) / 2;
                    act -= ((long) subsets[b].size * (subsets[b].size - 1)) / 2;
                    union(edges[i].u, edges[i].v);
                    int l = find(edges[i].u);
                    act += ((long) subsets[l].size * (subsets[l].size - 1)) / 2;
                }
                ans.add(new GPathQueries.Pair(edges[start].w, act));
                start = end + 1;
                end = end + 1;
            }
            for (int i = 0; i < m; i++) {
                int x = sc.nextInt();
                int a = Collections.binarySearch(ans, new GPathQueries.Pair(x, Long.MAX_VALUE), new Comparator<GPathQueries.Pair>() {

                    public int compare(GPathQueries.Pair a, GPathQueries.Pair b) {
                        return Integer.compare(a.x, b.x);
                    }
                });
                if (a < 0) {
                    a++;
                    a *= -1;
                    a--;
                    if (a < 0) {
                        out.print(0 + " ");
                        continue;
                    }
                }
                out.print(ans.get(a).y + " ");
            }
        }

        static class Subset {
            int parent;
            int size;

        }

        static class Edge {
            int u;
            int v;
            int w;

            public Edge(int u, int v, int w) {
                this.u = u;
                this.v = v;
                this.w = w;
            }

        }

        static class Pair {
            int x;
            long y;

            public Pair(int x, long y) {
                this.x = x;
                this.y = y;
            }

        }

    }

    static class inputClass {
        BufferedReader br;
        StringTokenizer st;

        public inputClass(InputStream in) {

            br = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}