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:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1249F
   {
      static int[][] dp;
      static LinkedList<Integer>[] edges;
      static int[] arr;
      static int K;
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         K = Integer.parseInt(st.nextToken());
         arr = new int[N+1];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i+1] = Integer.parseInt(st.nextToken());
         edges = new LinkedList[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new LinkedList<Integer>();
         for(int i=0; i < N-1; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            edges[b].add(a);
         }
         dp = new int[N+1][K+2];
         for(int i=1; i <= N; i++)
            Arrays.fill(dp[i], -1);
         par = new int[N+1];
         par[1] = -1;
         Queue<Integer> q = new LinkedList<Integer>();
         q.add(1);
         while(q.size() > 0)
         {
            int curr = q.poll();
            for(int next: edges[curr])
               if(par[next] == 0)
               {
                  par[next] = curr;
                  q.add(next);
               }
         }
         int res = 0;
         for(int d=0; d < K; d++)
            res = Math.max(res, dfs(1, d));
         System.out.println(res);
      }
      static int[] par;
      public static int dfs(int curr, int dist)
      {
         if(dp[curr][dist] != -1)
            return dp[curr][dist];
         int res = 0;
         if(dist == 0)
         {
            res = arr[curr];
            for(int next: edges[curr])
               if(next != par[curr])
                  res += dfs(next, K);
         }
         else
         {
            int small = dist-1;
            int large = Math.max(K-dist, small);
            ArrayList<Integer> children = new ArrayList<Integer>();
            for(int next: edges[curr])
               if(next != par[curr])
                  children.add(next);
            for(int i=0; i < children.size(); i++)
            {
               int temp = 0;
               for(int a=0; a < children.size(); a++)
               {
                  if(a == i)
                     temp += dfs(children.get(a), small);
                  else
                     temp += dfs(children.get(a), large);
               }
               res = Math.max(res, temp);
            }
         }
         if(dist < K)
            res = Math.max(res, dfs(curr, dist+1));
         return dp[curr][dist] = res;
      }
   }