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 = 200005;
inline int read() {
  int z = 0, x = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') x = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') z = z * 10 + c - '0', c = getchar();
  return z * x;
}
int n, m, a, b, c, he = 1;
struct qwe {
  int u, v, ne, w;
  bool operator<(const qwe x) const { return w < x.w; }
} e[N];
struct asd {
  int num, l;
  bool operator<(const asd x) const { return num < x.num; }
} q[N];
int head[N], k;
long long an[N], ans;
void adde(int u, int v, int w) {
  e[++k].v = v;
  e[k].u = u;
  e[k].w = w;
  e[k].ne = head[u];
  head[u] = k;
}
int fa[N], siz[N];
int find(int rt) { return fa[rt] == rt ? rt : fa[rt] = find(fa[rt]); }
void init() {
  for (register int q1 = 1; q1 <= n; q1++) fa[q1] = q1, siz[q1] = 1;
}
long long sum(int si) { return ((long long)(si - 1) * si) / 2; }
void hb(int r1, int r2) {
  ans -= sum(siz[r1]) + sum(siz[r2]);
  if (siz[r1] < siz[r2])
    fa[r1] = r2, siz[r2] += siz[r1], ans += sum(siz[r2]);
  else
    fa[r2] = r1, siz[r1] += siz[r2], ans += sum(siz[r1]);
}
int main() {
  n = read(), m = read();
  init();
  for (register int q1 = 1; q1 < n; q1++) {
    a = read(), b = read(), c = read();
    adde(a, b, c);
  }
  sort(e + 1, e + n);
  for (register int q1 = 1; q1 <= m; q1++) q[q1] = (asd){read(), q1};
  sort(q + 1, q + m + 1);
  for (register int q1 = 1; q1 <= m; q1++) {
    while (e[he].w <= q[q1].num && he < n)
      hb(find(e[he].u), find(e[he].v)), he++;
    an[q[q1].l] = ans;
  }
  for (register int q1 = 1; q1 <= m; q1++) printf("%lld\n", an[q1]);
  return 0;
}