树上寻宝

题号：NC307669
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

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

第二行包含  个正整数 ，相邻整数之间使用一个空格分隔。

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

- 对于所有评测用例，，，。

输出描述:

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

示例1

输入

复制

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

输出

复制

说明

- 走  步能到的结点：；
- 走  步能到的结点：；
- 走  步能到的结点：；

因此能到的结点为：，能获得的总价值为 。