Migrated from Lutece 3153 回忆与她皆失

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

我也曾想过尽力去挽救这段破碎的感情，

然而终究只是剩下了做工具的价值。

但我终将会向你证明我不是你口中所谓的废物，

最后，祝你幸福。

被白给的感情经历伤透了心的 Tri17 打算断绝跟部分妹妹的联系，但如果 Tri17 跟某个妹妹断绝关系，妹妹的跟班也会跟他断绝关系。 在 Tri17 的关系网中，总共有 $N$ 个妹妹，Tri17 跟第 $i$ 个的妹妹的亲密度为 $a_i$ ，每个妹妹要么没有跟班，要么有且仅有两个直接跟班，且跟班关系传递且不存在循环（即不存在 B 是 A 的，C 是 B 的，A 是 C 的）。 现在，Tri17 需要断绝跟 $K$ 个妹妹的关系，他想知道这么做之后能跟他保持联系的妹妹的亲密度之和最大为多少。

Input

第一行输入两个整数 $N$ 和 $K$ ，分别表示妹妹的数量和要断绝关系的数量。 第二行输入$N$ 个整数，分别表示跟妹妹的亲密度 $a_i$ 。 接下来 $N-1$ 行，每行输入两个整数 $u,v$ ，表示 $v$ 是 $u$ 的跟班。

Output

输出一个整数，即能留住的亲密度之和最大值。

Samples

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

24

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

4

Constraints

$1 \le K < N \le 1000,1\le a_i \le 10^6$

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming