【文件读写】本题使用文件读写：输入文件 cut.in，输出文件 cut.out。

时间限制：1000ms　内存限制：512MB

结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某灌溉管理处管辖着一片灌区。灌区内有 $n$ 个泵站，泵站之间由 $n-1$ 条渠道直接连通，且任意两个泵站之间都恰有一条由渠道连成的通路——这些泵站与渠道共同构成一棵树。泵站 $i$ 的日流量为 $w_i$，表示该泵站每天需要输送的水量。

为配合检修，管理处计划切断恰好 $k$ 条渠道。渠道被切断后，灌区被分为 $k+1$ 个互不相连的连通分区，任意两个泵站同属一个分区，当且仅当它们之间仍有未切断的渠道连通。每个分区的负荷定义为该分区内所有泵站日流量之和。管理处需要选定切断哪 $k$ 条渠道，使所有分区中最大分区负荷尽可能小。

请你求出：在切断恰好 $k$ 条渠道的所有可行方案中，最大分区负荷的最小可能值。

输入格式

从文件 cut.in 中读入数据。

• 第一行两个整数 $n, k$；
• 接下来 $n-1$ 行，每行两个整数 $u, v$，表示一条连接泵站 $u$ 与泵站 $v$ 的渠道；
• 最后一行 $n$ 个整数 $w_1, w_2, \dots, w_n$，依次表示 $1$ 号到 $n$ 号泵站的日流量。

输出格式

输出到文件 cut.out 中。

输出一行一个整数，表示最大分区负荷的最小可能值。

样例

样例 1 输入

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

样例 1 输出

12

样例 1 解释

切断渠道 $(1,2)$ 与 $(1,4)$ 后，灌区分为三个分区 $\{1,3\}$、$\{2,5\}$、$\{4,6\}$，负荷分别为 $8+4=12$、$3+2=5$、$5+1=6$，最大分区负荷为 $12$。

样例 2 输入

5 1
1 2
2 3
3 4
4 5
50 50 60 1 1

样例 2 输出

100

样例 2 解释

只切一刀时，切断渠道 $(2,3)$ 得到分区 $\{1,2\}$ 与 $\{3,4,5\}$，负荷分别为 $100$ 与 $62$，最大为 $100$。若切 $(1,2)$，分区 $\{2,3,4,5\}$ 负荷为 $112$；若切 $(3,4)$，分区 $\{1,2,3\}$ 负荷为 $160$，均更大。

样例 3 输入

4 0
1 2
2 3
3 4
5 3 9 2

样例 3 输出

19

样例 3 解释

$k=0$，不切断任何渠道，整个灌区为一个分区，负荷为 $5+3+9+2=19$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，$0 \le k \le n-1$；
• $1 \le w_i \le 10^9$；
• 渠道连接构成一棵树：无重边、无自环，任意两个泵站之间恰有一条由渠道连成的通路。

各测试点的约束如下：

• 特殊性质 A：每个泵站的度数不超过 $2$。