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.util.*;
import java.io.*;
public class G582
{
    static ArrayList<Integer> [] adj;
    public static void main(String [] args)
    {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt(); int m = sc.nextInt();
        adj = new ArrayList[n+1];
        for (int i = 1; i <= n; i++)adj[i] = new ArrayList<>();
        Edge [] e = new Edge[n-1];
        for (int i= 0; i < n - 1; i++) {
            int a = sc.nextInt(); int b = sc.nextInt();
            adj[a].add(b); adj[b].add(a);
            e[i] = new Edge(a, b, sc.nextInt());
        }
        Arrays.sort(e); int idx = 0;
        int large = n; int [] q = new int[m];
        for (int i = 0; i < m; i++) {
            q[i] = sc.nextInt();
        }
        long [] ret = new long [200001]; long cur = 0;
        UF dsu = new UF(n+1);
        for (int i = 0; i <= 200000; i++) {
            while (idx < n - 1 && e[idx].val <= i) {
                int a = dsu.find(e[idx].a); int b = dsu.find(e[idx].b);
                long first = ((long) dsu.size[a] * (dsu.size[a] - 1)) / 2;
                long second = ((long) dsu.size[b] * (dsu.size[b] - 1)) / 2;
                long next = ((long)(dsu.size[a] + dsu.size[b]) * (dsu.size[a] + dsu.size[b] - 1)) / 2;
                cur += (next - first - second);
                dsu.union(a, b);
                idx++;
            }
            ret[i] = cur;
        }
        for (int i = 0; i < m; i++) out.print(ret[q[i]] + " ");
        out.close();
    }


    static class Edge implements Comparable<Edge> {
        int a; int b; int val;
        Edge(int a , int b, int val) {
            this.a = a; this.b = b; this.val = val;
        }

        @Override
        public int compareTo(Edge o) {
            if (val == o.val) {
                if (a == o.a) return b - o.b; else return a - o.a;
            }
            return val - o.val;
        }
    }


    static class UF {
        private int[] parent;  // parent[i] = parent of i
        private byte[] rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
        private int count;     // number of components
        private int[] size;
        public UF(int n) {
            if (n < 0) throw new IllegalArgumentException();
            count = n;
            parent = new int[n];
            rank = new byte[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
                size[i] = 1;
            }
        }

        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];    // path compression by halving
                p = parent[p];
            }
            return p;
        }

        public int count() {
            return count;
        }

        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;

            // make root of smaller rank point to root of larger rank
            if (rank[rootP] < rank[rootQ]) {
                parent[rootP] = rootQ;
                size[rootQ] = size[rootQ] + size[rootP];
            }
            else if (rank[rootP] > rank[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] = size[rootP] + size[rootQ];
            }
            else {
                parent[rootQ] = rootP;
                size[rootP] = size[rootP] + size[rootQ];
                rank[rootP]++;
            }
            count--;
        }
    }


    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

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

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }



    }

}