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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
vector<vector<long long int> > matMul(vector<vector<long long int> > A,
                                      vector<vector<long long int> > B,
                                      long long int m) {
  int r1 = A.size(), r2 = B.size(), c1 = A[0].size(), c2 = B[0].size();
  vector<vector<long long int> > ans(r1);
  for (int i = 0; i < r1; i++)
    for (int j = 0; j < c2; j++) {
      long long int mul = 0;
      for (int k = 0; k < c1; k++) mul = (mul + A[i][k] * B[k][j]) % m;
      ans[i].push_back(mul);
    }
  return ans;
}
vector<vector<long long int> > matPow(vector<vector<long long int> > first,
                                      long long int n, long long int m) {
  int r = first.size(), c = first[0].size();
  vector<vector<long long int> > result(r);
  for (int i = int(0); i < int(r); i++)
    for (int j = int(0); j < int(c); j++) {
      if (i == j)
        result[i].push_back(1);
      else
        result[i].push_back(0);
    }
  while (n > 0) {
    if (n % 2 == 1) result = matMul(result, first, m);
    first = matMul(first, first, m);
    n = n / 2;
  }
  return result;
}
long long int mod = 1e9 + 7;
long long int pow1(long long int first, long long int n, long long int m) {
  long long int result = 1;
  while (n > 0) {
    first %= m;
    if (n % 2 == 1) result = (result * first) % m;
    first = (first * first) % m;
    n = n / 2;
  }
  return result;
}
long long int pow2(long long int first, long long int n) {
  long long int result = 1;
  while (n > 0) {
    if (n % 2 == 1) result = (result * first);
    first = (first * first);
    n = n / 2;
  }
  return result;
}
long long int modInverse(long long int A, long long int M) {
  return pow1(A, M - 2, M);
}
long long int f[1000001];
void fact() {
  f[0] = f[1] = 1;
  for (int i = 2; i <= 1e6; i++) f[i] = (f[i - 1] * i) % mod;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
const int size = 1e6 + 1;
int a[size], Size[size];
int root(int i) {
  while (i != a[i]) {
    a[i] = a[a[i]];
    i = a[i];
  }
  return i;
}
long long int cal(long long int z) {
  z = z * (z - 1);
  z /= 2;
  return z;
}
long long int ans;
void fun(int u, int v) {
  int r1 = root(u), r2 = root(v);
  if (r1 == r2) return;
  ans -= cal(Size[r1]);
  ans -= cal(Size[r2]);
  a[r2] = r1;
  Size[r1] += Size[r2];
  ans += cal(Size[r1]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  int n, m;
  cin >> n >> m;
  for (int i = int(0); i < int(n + 1); i++) {
    a[i] = i;
    Size[i] = 1;
  }
  vector<pair<int, pair<int, int> > > edge;
  vector<int> E;
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    edge.push_back(make_pair(w, make_pair(u, v)));
    E.push_back(w);
  }
  sort(edge.begin(), edge.end());
  sort(E.begin(), E.end());
  vector<pair<int, int> > query;
  for (int i = int(0); i < int(m); i++) {
    int z;
    cin >> z;
    query.push_back(make_pair(z, i));
  }
  long long int ANS[m];
  sort(query.begin(), query.end());
  int s = 0;
  for (int i = int(0); i < int(m); i++) {
    int id = upper_bound(E.begin(), E.end(), query[i].first) - E.begin() - 1;
    for (int j = s; j <= id; j++) {
      fun(edge[j].second.first, edge[j].second.second);
    }
    ANS[query[i].second] = ans;
    s = id + 1;
  }
  for (int i = int(0); i < int(m); i++) cout << ANS[i] << " ";
  return 0;
}