该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

不是哥们，怎么怯战蜥蜴都出到 VII 了？

题目描述

坎格鲁斯普雷有一棵有 $n$ 个节点的有根树，其中 $1$ 号节点为根节点。

在这棵树上的每个节点都有一个物品，第 $i$ 个节点上的物品价值为 $w_i$ 。

定义以 $i$ 号节点为根做树形背包的过程如下：

你有一个体积为 $k$ 的背包，然后你需要选择一些在以 $i$ 号节点为根的子树中的节点（可以一个节点都不选），并把这些节点上的物品全部装进你的背包中，这些节点需要满足以下要求：

• 若选择了一个非 $i$ 号节点的节点，那么必须要选择它在子树内的父亲。
• 选择的节点数量不能大于 $k$ 。

做树形背包所得到的价值总和即为选择的节点上的所有物品的价值之和。

现在，坎格鲁斯普雷和袋鼠将军正在这棵树上进行游戏，游戏的过程如下：

• 坎格鲁斯普雷先在树上选择一个节点（不能是这棵树的叶子），然后袋鼠将军选择坎格鲁斯普雷选择的节点的任意一个儿子。
• 之后，他们两个分别以自己选择的节点为根做树形背包，坎格鲁斯普雷做背包的时候不能选择袋鼠将军选的那个节点所表示的子树的任何一个节点。
• 定义一名玩家的得分为他做树形背包所得到的价值总和。
• 定义游戏的得分为坎格鲁斯普雷的得分减去袋鼠将军的得分。

坎格鲁斯普雷想最大化游戏的得分，而袋鼠将军想最小化游戏的得分，假设他们两个都是绝顶聪明的，那么游戏的得分最终将会是多少？

输入格式

输入第一行两个整数 $n$ , $k$ ,分别表示树的大小以及背包的体积。 $(2 \leq n \leq 10^5,1 \leq k \leq 300)$

输入第二行 $n$ 个整数 $w_i$ ，含义见题意。 $(1 \leq w_i \leq 10^6)$

之后 $(n-1)$ 行，每行两个整数 $u_i$ , $v_i$ ,表示树内存在一条边连接 $u_i$ 和 $v_i$ 节点。 $(1 \leq u_i,v_i \leq n)$

输出格式

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

输入输出样例

输入 #1

6 2
10 5 3 3 6 8
1 2
1 3
2 4
3 5
3 6

输出 #1

2

说明与提示

对于样例 #1:

当两人都做出最优决策的时候，坎格鲁斯普雷会选择 $2$ 号节点，袋鼠将军会选择 $4$ 号节点，此时游戏的得分为 $5-3=2$ 分。注意背包并不一定要装满。