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.lang.*;
import java.util.*;
import java.io.*;

public class Main {
    void solve() {
       int n=ni(),m=ni();
       Node p[]=new Node[n-1];
       for(int i=0;i<n-1;i++) p[i]=new Node(ni(),ni(),ni());
       Arrays.sort(p);

       ans=new long[200001];
       F=new int[n+1];
       sz=new int[n+1];
       for(int i=1;i<=n;i++){
           F[i]=i;
           sz[i]=1;
       }
       for(int i=0;i<n-1;i++){
           union(p[i].u,p[i].v,p[i].w);
       }
       for(int i=1;i<=200000;i++) ans[i]+=ans[i-1];
       while(m-->0){
           int w=ni();
           pw.print(ans[w]+" ");
       }
       pw.println("");
    }
    int F[];
    int sz[];
    long ans[];
    int root(int a){
        while(a!=F[a]){
            F[a]=F[F[a]];
            a=F[a];
        }
        return a;
    }
    void union(int u,int v,int w){
        int x=root(u),y=root(v);
        if(sz[x]>sz[y]){
            int tmp=x; x=y; y=tmp;
        }

        ans[w]+=(sz[x]*1L*sz[y]);
        sz[y]+=sz[x];
        F[x]=y;
    }

    class Node implements Comparable<Node>{
        int u;
        int v;
        int w;
        public Node(int u,int v,int w){
            this.u=u;
            this.v=v;
            this.w=w;
        }
        public int compareTo(Node c){
            return Integer.compare(this.w,c.w);
        }
    }

    long M = (long)1e9+7;
    // END
    PrintWriter pw;
    StringTokenizer st;
    BufferedReader br;

    void run() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
    }
    public static void main(String[] args) throws Exception {
        new Main().run();
    }

    String ns() {
        while (st == null || !st.hasMoreElements()) {

            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    String nextLine() throws Exception {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            throw new Exception(e.toString());
        }
        return str;
    }

    int ni() {
        return Integer.parseInt(ns());
    }

    long nl() {
        return Long.parseLong(ns());
    }

    double nd() {
        return Double.parseDouble(ns());
    }
}