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.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        int n = in.nextInt();
        int m = in.nextInt();
        int MAX_W = 200_005;
        ArrayList<HashSet<Pair>> list = new ArrayList<HashSet<Pair>>();
        for (int i=0;i<=MAX_W;i++) {
            HashSet<Pair> add = new HashSet<Pair>();
            list.add(add);
        }
        for (int i=0;i<n-1;i++) {
            int u = in.nextInt()-1;
            int v = in.nextInt()-1;
            Pair pair = new Pair(Math.min(u, v), Math.max(u, v));
            int w = in.nextInt();
            list.get(w).add(pair);
        }

        UnionFind uf = new UnionFind(n);
        long[] ans = new long[MAX_W];
        for (int i=1;i<MAX_W;i++) {
            long tmp = ans[i-1];
            for (Pair p : list.get(i)) {
                int u = p.x;
                int v = p.y;
                if (uf.root(u) != uf.root(v)) {
                    long minus = (long)uf.size(u)*(uf.size(u)-1)/2+(long)uf.size(v)*(uf.size(v)-1)/2;
                    long plus = (long)(uf.size(u)+uf.size(v))*(uf.size(u)+uf.size(v)-1)/2;
                    tmp += plus-minus;
                }
                uf.connect(u, v);
            }
            ans[i] = tmp;
        }

        StringBuilder sb = new StringBuilder();
        for (int i=0;i<m;i++) {
            int q = in.nextInt();
            sb.append(ans[q]);
            if (i != m-1) sb.append(" ");
        }
        out.println(sb);

        out.close();
    }

static class Pair{
    public int x;
    public int y;
    public Pair(int x,int y) {
        this.x=x;
        this.y=y;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Pair) {
            Pair other = (Pair) obj;
            return other.x==this.x && other.y==this.y;
        }
        return false;
    }
    @Override
    public int hashCode() {
        return Objects.hash(this.x,this.y);
    }
}

static class UnionFind {
    List<Integer> Parent;
    UnionFind(int N) {
        Parent = new ArrayList<Integer>();
        Integer[] values = new Integer[N];
        Arrays.fill(values, -1);
        Parent.addAll(Arrays.asList(values));
    }
    int root(int A) {
        if (Parent.get(A) < 0)
            return A;
        int root = root(Parent.get(A));
        Parent.set(A, root);
        return root;
    }
    int size(int A) {
        return -Parent.get(root(A));
    }

    boolean connect(int A, int B) {
        A = root(A);
        B = root(B);
        if (A == B) {
            return false;
        }

        if (size(A) < size(B)) {
            int temp = A;
            A = B;
            B = temp;
        }

        Parent.set(A, Parent.get(A) + Parent.get(B));
        Parent.set(B, A);

        return true;
    }
}

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

    }
}