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:
/*
Stay innocent, be naive. 
But still dream big. 
Dream big to the point that it is beyond your ability and endeavour to achieve it. 
So dream big and don’t lose your innocence.
*/
import java.util.*;
import java.io.*;

   public class G
   {
      public static void main(String args[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());
         Edge[] arr = new Edge[N-1];
         for(int i=0; i < N-1; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arr[i] = new Edge(a, c, v);
         }
         Query[] qe = new Query[M];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < M; i++)
            qe[i] = new Query(i, Integer.parseInt(st.nextToken()));
         //sort
         Arrays.sort(qe);
         Arrays.sort(arr);
         //
         int[] tree = new int[N+1];
         for(int i=0; i <= N; i++)
            tree[i] = i;
         int[] sizes = new int[N+1];
         Arrays.fill(sizes, 1);
         DSU dsu = new DSU(tree, sizes);
         //
         long[] res = new long[M];
         int dex = 0;
         //solve
         long tempcount = 0L;
         for(Query q: qe)
         {
            int limit = q.weight;
            while(dex < arr.length && arr[dex].weight <= limit)
            {
               //process
               int a = arr[dex].x;
               int b = arr[dex].y;
               tempcount -= hs(sizes[dsu.find(a)]);
               tempcount -= hs(sizes[dsu.find(b)]);
               dsu.merge(a, b);
               tempcount += hs(sizes[dsu.find(a)]);
               dex++;
            }
            res[q.i] = tempcount;
         }
         StringBuilder sb = new StringBuilder();
         for(long x: res)
            sb.append(x+" ");
         System.out.println(sb.toString());
      }
      public static long hs(int n)
      {
         return ((long)n*(n-1))/2;
      }
   }
   class Edge implements Comparable<Edge>
   {
      public int x;
      public int y;
      public int weight;
      
      public Edge(int a, int b, int c)
      {
         x = a;
         y = b;
         weight = c;
      }
      public int compareTo(Edge oth)
      {
         return weight-oth.weight;
      }
   }
   class Query implements Comparable<Query>
   {
      public int i;
      public int weight;
      
      public Query(int b, int c)
      {
         i = b;
         weight = c;
      }
      public int compareTo(Query oth)
      {
         return weight-oth.weight;
      }
   }
   class DSU
   {
      public int[] dsu;
      public int[] size;
      
      public DSU(int[] a, int[] b)
      {
         dsu = a;
         size = b;
      }
      public int find(int x) 
      {
   		return dsu[x] == x ? x : (dsu[x] = find(dsu[x]));
   	}
   	public void merge(int x, int y) 
      {
   		int fx = find(x);
   		int fy = find(y);
   		size[fy] += size[fx];
   		dsu[fx] = fy;
   	}
   }