问题描述

这天，你通关了魔女的夜宴，准备去攻略一个新的游戏。这款游戏有 $n$ 个 事件 ，某些事件可以通过不同的选择支到达其他事件。所有事件和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个事件有一个新鲜度 $a_i$ ，你每遇到一个事件会获得当前事件的新鲜度，然后这个事件的新鲜度将会变为 $0$ 。

现在，你马上要被你的好队长拉去写南宁周赛了。你剩余的时间只够你攻略 $k$ 次该游戏（每次必须要到达结局才算是一次攻略），所以你最多可以攻略该游戏 $k$ 次，你想找出你最多能获取多少新鲜度。

输入格式

第一行输入两个整数 $n, k$ 。

第二行输入 $n$ 个整数 $a_i$ 。

接下来 $n-1$ 行每行包含两个整数 $u, v$ ，表示节点 $u$ 是节点 $v$ 的父节点。

输出格式

输出你最多能获取多少新鲜度。

输入样例

5 2
1 2 3 4 5
2 3
2 4
4 1
2 5

输出样例

12

评测数据规模

数据范围保证：$1 \le n, k \le 2 \times 10^5$ ， $1 \le a_i \le 10^9$ ， $1 \le u, v \le n$。