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 F {
    public static class Edge implements Comparable<Edge>{
        int from;
        int to;
        int w;
        public Edge(int f, int t, int w){
            this.from = f;
            this.to = t;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return this.w - o.w;
        }
    }
    public static class z implements Comparable<z>{
        int ind;
        int q;
        public z(int i, int q){
            this.ind = i;
            this.q = q;
        }

        @Override
        public int compareTo(z o) {
            return this.q - o.q;
        }
    }
    public static class DSU {
        public int[] parent;
        public int[] rank;
        public int size;
        public long[] sizee;

        public DSU(int size) {
            this.parent = new int[size];
            this.rank = new int[size];
            this.size = size;
            this.sizee = new long[size];
            for (int i = 0; i < size; ++i) {
                parent[i] = i;
                sizee[i] = 1;
            }
        }

        public int par(int node) {
            if (parent[node] == node) {
                return node;
            }
            parent[node] = par(parent[node]);
            return parent[node];
        }

        public boolean un(int x, int y) {
            x = par(x);
            y = par(y);
            return x == y;
        }
        public long get(int x){
            x = par(x);
            return sizee[x] * (sizee[x] - 1) / 2;
        }
        public void unite(int x, int y) {
            x = par(x);
            y = par(y);
            if (x == y) {
                return;
            }
            --size;
            parent[x] = y;
            sizee[y] += sizee[x];
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long[] answers = new long[m];
        ArrayList<Edge> edges = new ArrayList<>();
        ArrayList<z> zap = new ArrayList<>();
        DSU dsu = new DSU(n);
        for(int i = 0; i < n - 1; ++i){
            st = new StringTokenizer(reader.readLine());
            edges.add(new Edge(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken())));
        }
        Collections.sort(edges);
        st = new StringTokenizer(reader.readLine());
        for(int i = 0; i < m; ++i){
            zap.add(new z(i, Integer.parseInt(st.nextToken())));
        }
        Collections.sort(zap);
        int last = 0;
        long ans = 0;
        for(int i = 0; i < m; ++i){
            int w_max = zap.get(i).q;
            while(last < n - 1 && edges.get(last).w <= w_max){
                ans -= dsu.get(edges.get(last).from);
                ans -= dsu.get(edges.get(last).to);
                dsu.unite(edges.get(last).from, edges.get(last).to);
                ans += dsu.get(edges.get(last).to);
                ++last;
            }
            answers[zap.get(i).ind] = ans;
        }
        for(int i = 0; i < m; ++i){
            writer.print(answers[i] + " ");
        }
        writer.close();
    }
}