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 N = 2e5 + 5;
int rnk[N], parent[N], freq[N], Q[N];
long long int Q1[N];
bool visited[N];
vector<vector<pair<int, int>>> wt(N);
int findParent(int node) {
  if (parent[node] == node) {
    return node;
  }
  parent[node] = findParent(parent[node]);
  return parent[node];
}
long long int addEdge(int a, int b) {
  int pa = findParent(a);
  int pb = findParent(b);
  long long int ans = 1LL * freq[pa] * freq[pb];
  if (pa == pb) {
    return 0LL;
  }
  if (rnk[pa] > rnk[pb]) {
    parent[pb] = pa;
    freq[pa] += freq[pb];
  } else if (rnk[pa] == rnk[pb]) {
    parent[pb] = pa;
    freq[pa] += freq[pb];
    rnk[pa]++;
  } else {
    parent[pa] = pb;
    freq[pb] += freq[pa];
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int e, q;
  cin >> e >> q;
  for (int i = 0; i < N - 2; i++) {
    parent[i] = i;
    freq[i] = 1;
  }
  for (int i = 0; i < e - 1; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    pair<int, int> p = make_pair(x, y);
    wt[w].push_back(p);
  }
  int M = 0;
  for (int i = 0; i < q; i++) {
    cin >> Q[i];
    M = max(Q[i], M);
    Q1[Q[i]] = 1;
  }
  long long int ans = 0;
  for (int i = 1; i <= M; i++) {
    for (auto elm : wt[i]) {
      ans += addEdge(elm.first, elm.second);
    }
    if (Q1[i] == 1) {
      Q1[i] = ans;
    }
  }
  for (int i = 0; i < q; i++) {
    cout << Q1[Q[i]] << ' ';
  }
  return 0;
}