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:
/**
 * @author derrick20
 */

import java.io.*;
import java.util.*;

public class MaxWeightSubset3 {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        N = sc.nextInt();
        K = sc.nextInt();
        wt = new long[N];
        for (int i = 0; i < N; i++) {
            wt[i] = sc.nextLong();
        }
        adjList = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            adjList[u].add(v);
            adjList[v].add(u);
        }
        K++;
        dp = new long[N][K + 1];
        vis = new boolean[N][K + 1];
        solve(0, -1, 0);
        out.println(best);
        out.close();
    }

    static ArrayList<Integer>[] adjList;
    static int N, K;
    static long[][] dp;
    static boolean[][] vis;
    static long[] wt;
    static long best;

    static long solve(int node, int par, int remDist) {
        if (vis[node][remDist]) {
            return dp[node][remDist];
        }
        else {
            vis[node][remDist] = true;
            ArrayList<Integer> children = new ArrayList<>();
            for (int x : adjList[node]) {
                if (x != par) {
                    children.add(x);
                }
            }
            int size = children.size();
            long[] total = new long[K + 1];
            for (int dist = 0; dist <= K; dist++) {
                for (int i = 1; i <= size; i++) {
                    int adj = children.get(i - 1);
                    total[dist] += solve(adj, node, dist);
                }
            }
            if (remDist == 0) {
                long take = wt[node] + total[K - 1];
                long skip = 0;
                for (int i = 1; i <= size; i++) {
                    int adj = children.get(i - 1);
                    for (int dist = 1; dist - 1 <= K - 1 - dist; dist++) {
                        int big = K - 1 - dist;
                        skip = Math.max(skip, dp[adj][dist - 1] + total[big] - dp[adj][big]);
                    }
                }
                dp[node][remDist] = Math.max(dp[node][remDist], Math.max(take, skip));
            }
            else {
                if (remDist - 1 <= K - remDist - 1) {
                    int big = K - remDist - 1;
                    for (int i = 1; i <= size; i++) {
                        int adj = children.get(i - 1);
                        long small = dp[adj][remDist - 1];
                        dp[node][remDist] = Math.max(dp[node][remDist], small + total[big] - dp[adj][big]);
                    }
                }
                int bigger = Math.max(remDist - 1, K - remDist - 1);
                dp[node][remDist] = Math.max(dp[node][remDist], total[bigger]);
            }

            best = Math.max(best, dp[node][remDist]);
            return dp[node][remDist];
        }
    }

    static class FastScanner {
        public int BS = 1 << 16;
        public char NC = (char) 0;
        byte[] buf = new byte[BS];
        int bId = 0, size = 0;
        char c = NC;
        double cnt = 1;
        BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1)
                    return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC)
                c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-')
                    neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) {
                c = getChar();
            }
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) {
                c = getChar();
            }
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32)
                return true;
            while (true) {
                c = getChar();
                if (c == NC)
                    return false;
                else if (c > 32)
                    return true;
            }
        }
    }
}