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

题目描述

$D$ 国有 $n$ 个城市，由于城市之间并没有公路，交通十分不方便。

$D$ 国国王希望修建 $n−1$ 条公路，使得对于任意两个城市，都可以通过公路互相到达。

建造公路的任务由各个城市负责，具体来说，每个城市都会给出建造公路的费用，第 $i$ 个城市修建公路的费用为 $d_i$ 。而对于一条连接 $x,y$ 两座城市的公路，它的建造任务会由 $x,y$ 两座城市中修建费用较小的城市来负责修建。整个建造方案的费用为每条公路的建造费用之和。

工程师给出了一个建造方案，但国王认为方案成本略高，他希望工程师修改方案。但出于某种原因，工程师只能在方案中更改不超过 $k$ 条公路，并且要保证更改后任意两座城市仍然可以通过公路相互到达。你能帮助他算一算在更改方案后最小的建造费用吗？

输入格式

第一行输入两个正整数 $n,k(1≤n≤10^5,0≤k<n)$。

接下来一行输入 $n$ 个正整数 $d_i(1≤d_i≤n)$ 表示第 $i$ 个城市建造公路的费用。

接下来 $n−1$ 输入初始的建造方案，每个行包含两个正整数 $x,y(1≤x,y≤n)$，代表初始建造方案。保证输入是一个合法的方案。

输出格式

输出一行一个正整数表示最小的成本。

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

5

解释 #1

将第一条公路修改为连接城市 $2$ 和城市 $5$ 的公路是一个最优的更改方案。