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;
namespace IO {
template <class T>
inline bool read(T &x) {
  int c = getchar();
  int sgn = 1;
  while (~c && c < '0' || c > '9') {
    if (c == '-') sgn = -1;
    c = getchar();
  }
  for (x = 0; ~c && '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  x *= sgn;
  return ~c;
}
}  // namespace IO
namespace Utility {
template <typename T>
T gcd(T a, T b) {
  return a ? gcd(b % a, a) : b;
}
template <typename T>
T lcm(T a, T b) {
  return (a / gcd(a, b) * b);
}
template <typename T>
inline T addmod(T a, T b, T mod) {
  T c = a + b;
  return c > mod ? c - mod : c;
}
template <typename T>
inline T submod(T a, T b, T mod) {
  T c = a - b;
  return c < mod ? c + mod : c;
}
template <typename T>
inline T mulmod(T a, T b, T mod) {
  return a * 1LL * b % mod;
}
template <typename T>
T exEuclid(T a, T b, T &x, T &y) {
  x = 0, y = 1;
  if (a == 0) return b;
  T x1, y1;
  T d = exEuclid(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
template <typename T>
T modInv(T a, T mod) {
  T x, y;
  exEuclid(a, mod, x, y);
  return x < 0 ? x + mod : x;
}
template <typename T>
T bigmod(T b, T p, T mod) {
  T ret = b > 0;
  while (p) {
    if (p & 1) ret = mulmod(ret, b, mod);
    p >>= 1, b = mulmod(b, b, mod);
  }
  return ret;
}
}  // namespace Utility
using namespace IO;
using namespace Utility;
const int INF = 2000000009;
const int MX = 205;
const double EPS = 1e-9;
const double PI = acos(-1.0);
const int MOD = 1e9 + 7;
vector<int> g[MX], g2[MX];
int a[MX];
int dp[MX][MX][MX];
int n, k;
void dfs0(int u, int p = -1) {
  for (int v : g2[u])
    if (v != p) {
      g[u].push_back(v);
      dfs0(v, u);
    }
}
int dfs(int u, int p, int d) {
  if (d < 0) d = 0;
  if (p >= (int)g[u].size()) {
    if (p == 0 && d == 0) return a[u];
    return 0;
  }
  int &ret = dp[u][p][d];
  if (ret != -1) return ret;
  ret = 0;
  if (d == 0 && p == 0) {
    ret = a[u];
    for (int v : g[u]) ret += dfs(v, 0, k);
  }
  ret = max(ret, dfs(u, p + 1, d));
  for (int i = max(d - 1, 0); i <= k; i++) {
    ret = max(ret, dfs(g[u][p], 0, i) + dfs(u, p + 1, max(d, k - i)));
  }
  return ret;
}
int main() {
  n = ({
    int a;
    read(a);
    a;
  }),
  k = ({
    int a;
    read(a);
    a;
  });
  for (int i = 1; i <= n; i++)
    a[i] = ({
      int a;
      read(a);
      a;
    });
  for (int i = 1; i < n; i++) {
    int u = ({
      int a;
      read(a);
      a;
    }),
        v = ({
          int a;
          read(a);
          a;
        });
    g2[u].push_back(v);
    g2[v].push_back(u);
  }
  dfs0(1);
  memset(dp, -1, sizeof(dp));
  int ans = dfs(1, 0, 0);
  printf("%d\n", ans);
  return 0;
}