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.util.*;
import javafx.util.*;
public class Solution
{
       static int parent[];
       static int size[];
       
       static int getParent(int v)
       {
              if(parent[v] == v)
              {
                     return v;
              }
              
              return parent[v] = getParent(parent[v]);
       }
       
       static void union(int a , int b)
       {
              a = getParent(a);
              b = getParent(b);
              
              if(size[a] < size[b])
              {
                     int temp = a;
                     a = b;
                     b = temp;
              }
              
              parent[b] = a;
              size[a] += size[b];
       }
      static long get(long n)
       {
              return n*(n-1)/2;
       }
       public static void main(String []args)
       {
              Scanner sc = new Scanner(System.in);
              int n = sc.nextInt();
              int q = sc.nextInt();
              LinkedList<Pair<Integer,Integer>> arr[] = new LinkedList[200001];
              for(int i = 1 ; i <= 200000 ; i++)
              {
                     arr[i] = new LinkedList<Pair<Integer,Integer>>();
              }
              long res = 0;
              parent = new int[n+1];
              size = new int[n+1];
              for(int i = 1 ; i<= n ; i++)
              {
                     size[i] = 1;
                     parent[i] = i;
              }
              for(int i = 1 ; i <= n-1 ; i++)
              {
                     int x = sc.nextInt();
                     int y = sc.nextInt();
                     int c = sc.nextInt();
                     arr[c].add(new Pair<Integer,Integer>(x,y));
              }
              long ans[] = new long[200001];
              for(int i = 1 ; i <= 200000 ; i++)
              {
                     for(Pair<Integer,Integer> p : arr[i])
                     {
                            res = res-get((long)size[getParent(p.getKey())])-get((long)size[getParent(p.getValue())])
                             + get((long)(size[getParent(p.getKey())]+size[getParent(p.getValue())]));
                             
                             union(p.getKey(),p.getValue());
                           //  System.out.println(size[p.getKey()] + "  " + size[p.getValue()]);
                     }
                   ans[i] = res;  
                     
              }
              
              StringBuffer str = new StringBuffer("");
              while(q-- > 0)
              {
                     str.append(ans[sc.nextInt()] + " ");
              }
              System.out.println(str);
       }
}