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:
// package codeforce.Training1900;

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class PathQueries {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int t = 1;
        for (int i = 0; i < t; i++) {
            solve(sc, pw);
        }
        pw.close();
    }

    static class Edge{
        int from, to, weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    static Edge[] edges;
    static void solve(Scanner in, PrintWriter out){
        int n = in.nextInt(), m = in.nextInt();
        edges = new Edge[n - 1];
        for (int i = 0; i < n - 1; i++) {
            edges[i] = new Edge(in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
        }
        int[][] qs = new int[m][];
        for (int i = 0; i < m; i++) {
            qs[i] = new int[]{in.nextInt(), i};
        }
        Arrays.sort(qs, (a, b) -> (a[0] - b[0]));
        Arrays.sort(edges, (a, b) -> (a.weight - b.weight));
        int[] pars = new int[n];
        Arrays.fill(pars, -1);
        long tot = 0;
        long[] ans = new long[m];
        for (int i = 0, j = 0; i < m; i++) {
            while (j < n - 1 && edges[j].weight <= qs[i][0]){
                int f = edges[j].from, t = edges[j].to, idf, idt;
                if ((idf = find(f, pars) )!= (idt = find(t, pars))){
                    int vf = -pars[idf], vt = -pars[idt];
                    tot -= (vf * (vf - 1l)) / 2;
                    tot -= (vt * (vt - 1l)) / 2;
                }
                union(f, t, pars);
                int par = find(f, pars);
                tot += (-pars[par] * (-pars[par] - 1l) / 2);
                j++;
            }
//            System.out.println(qs[i][1]+ " fff");
            ans[qs[i][1]] = tot;
        }
        for (int i = 0; i < m; i++) {
            out.print(ans[i]+" ");
        }
        out.println();
    }

    static int find(int i, int[] par){
        if (par[i] < 0) return i;
        return par[i] = find(par[i], par);
    }
    static boolean union(int i, int j, int[] par){
        int pi = find(i, par);
        int pj = find(j, par);
        if (pi == pj) return false;
        if (par[pi] < par[pj]){
            par[pi] += par[pj];
            par[pj] = pi;
        }else{
            par[pj] += par[pi];
            par[pi] = pj;
        }
        return true;
    }

    // Use this instead of Arrays.sort() on an array of ints. Arrays.sort() is n^2
    // worst case since it uses a version of quicksort. Although this would never
    // actually show up in the real world, in codeforces, people can hack, so
    // this is needed.
    static void ruffleSort(int[] a) {
        //ruffle
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            int oi=r.nextInt(n), temp=a[i];
            a[i]=a[oi];
            a[oi]=temp;
        }

        //then sort
        Arrays.sort(a);
    }
}