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;
const int inf = 1 << 30;
const long long linf = 1LL << 62;
const int MAX = 510000;
long long dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
long long dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const double pi = acos(-1);
const double eps = 1e-7;
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
inline void print2(T1 a, T2 b) {
  cout << a << " " << b << endl;
}
template <typename T1, typename T2, typename T3>
inline void print3(T1 a, T2 b, T3 c) {
  cout << a << " " << b << " " << c << endl;
}
const int mod = 1e9 + 7;
struct UnionFind {
  vector<long long> p;
  vector<long long> rank;
  vector<long long> cnt;
  UnionFind(long long n) {
    rank.resize(n, 0);
    p.resize(n, 0);
    cnt.resize(n, 0);
    for (long long i = 0; i < (n); i++) {
      p[i] = i;
      rank[i] = 0;
      cnt[i] = 1;
    }
  }
  long long find(long long x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
  }
  bool same(long long x, long long y) { return find(x) == find(y); }
  void unite(long long x, long long y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] > rank[y]) {
      p[y] = x;
      cnt[x] += cnt[y];
    } else {
      p[x] = y;
      cnt[y] += cnt[x];
      if (rank[x] == rank[y]) rank[y]++;
    }
  }
  long long size(long long x) { return cnt[find(x)]; }
};
void solve() {
  long long n, q;
  cin >> n >> q;
  vector<tuple<long long, long long, long long> > a(n - 1);
  for (long long i = 0; i < (n - 1); i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    a[i] = tie(w, u, v);
  }
  sort((a).begin(), (a).end());
  vector<pair<long long, long long> > query(q);
  vector<long long> ans(q, 0);
  for (long long i = 0; i < (q); i++) {
    cin >> query[i].first;
    query[i].second = i;
  }
  sort((query).begin(), (query).end());
  long long now = 0;
  long long edge = 0;
  UnionFind uf(n);
  for (long long i = 0; i < (q); i++) {
    long long id = query[i].second;
    if (now == query[i].first)
      ans[id] = ans[query[i - 1].second];
    else {
      if (i > 0) ans[id] = ans[query[i - 1].second];
      now = query[i].first;
      while (edge < n - 1) {
        long long u, v, w;
        tie(w, u, v) = a[edge];
        if (w > now) break;
        long long uu = uf.size(u);
        long long vv = uf.size(v);
        ans[id] -= uu * (uu - 1) / 2 + vv * (vv - 1) / 2;
        uf.unite(u, v);
        long long nu = uf.size(u);
        ans[id] += nu * (nu - 1) / 2;
        edge++;
      }
    }
  }
  for (long long i = 0; i < (q); i++) cout << ans[i] << " ";
  cout << endl;
}
int main() {
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}