题目描述

小蓝正在一棵含有 $n$ 个结点的树的根结点 $1$ 上，他准备在这棵树上寻宝。结点 $i$ 上有一个物品，价值为 $w_i$。然而，小蓝每次寻宝只能从根节点出发走不超过 $k$ 步，每步只能选择走 $1$ 条边或者 $2$ 条边，之后会自动拾取最终停留的结点上的物品并被传送回根结点。请求出小蓝最终能获得的物品的总价值。

输入格式

输入的第一行包含两个正整数 $n, k$，用一个空格分隔。

第二行包含 $n$ 个正整数 $w_1, w_2, \cdots, w_n$，相邻整数之间使用一个空格分隔。

接下来 $n-1$ 行，每行包含两个正整数 $u_i, v_i$，用一个空格分隔，表示结点 $u_i$ 和结点 $v_i$ 之间有一条边。

输出格式

输出一行包含一个整数表示答案。

8 2
6 3 3 1 5 4 3 4
1 2
2 3
2 4
4 5
5 6
6 7
7 8

22

提示

样例说明

• 走 $0$ 步能到的结点：$1$；
• 走 $1$ 步能到的结点：$2, 3, 4$；
• 走 $2$ 步能到的结点：$3, 4, 5, 6$；

因此能到的结点为：$1, 2, 3, 4, 5, 6$，能获得的总价值为 $22$。

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1 \leq n \leq 15$；
• 对于所有评测用例，$0 \leq k < n \leq 10^5$，$1 \leq w_i \leq 10^6$，$1 \leq u_i, v_i \leq n$。