题目描述

在逃亡者的面前有一个迷宫，这个迷宫由 $n$ 个房间和 $n-1$ 条双向走廊构成，每条走廊会链接不同的两个房间，所有的房间都可以通过走廊互相到达。换句话说，这是一棵树。

逃亡者会选择一个房间进入迷宫，走过若干条走廊并走出迷宫，但他永远不会走重复的走廊。

在第 $i$ 个房间里，有 $F_i$​​ 个铁球，每当一个人经过这个房间时，他就会受到铁球的阻挡。逃亡者手里有 $V$ 个磁铁，当他到达一个房间时，他可以选择丢下一个磁铁（也可以不丢），将与这个房间相邻的所有房间里的铁球吸引到这个房间。这个过程如下：

1. 逃亡者进入房间。
2. 逃亡者丢下磁铁。
3. 逃亡者走出房间。
4. 铁球被吸引到这个房间。

注意逃亡者只会受到这个房间原有的铁球的阻拦，而不会受到被吸引的铁球的阻挡。

在逃亡者走出迷宫后，追逐者将会沿着逃亡者走过的路径穿过迷宫，他会碰到这条路径上所有的铁球。

请帮助逃亡者选择一条路径，使得追逐者遇到的铁球数量减去逃亡者遇到的铁球数量最大化。

输入格式

第一行两个空格隔开的整数整数 $n$ 和 $V$。 第二行 $n$ 个空格隔开的整数表示 $F_i$​​。 之后的 $n-1$ 行，每行两个空格隔开的整数 $x$ 和 $y$，表示有一条走廊连接编号为 $x$ 和编号为 $y$ 的房间。

输出格式

输出一个整数表示最优情况下追逐者遇到的铁球数量减去逃亡者遇到的铁球数量。

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

36

提示

样例解释

有一个最优方案如下：

• 从 $6$ 号房间进入迷宫并丢下第一个磁铁，他遇到了 $5$ 个铁球，这个时候 $6$ 号房间会有 $27$ 个铁球，而 $5$ 号，$7$ 号，$8$ 号，$9$ 号房间都没有铁球。
• 走到 $7$ 号房间丢下第二个磁铁并走出迷宫，他遇到了 $0$ 个铁球，这个时候 $7$ 号房间会有 $41$ 个铁球，而 $2$ 号，$4$ 号，$6$ 号，$10$ 号房间会没有铁球。

在这个过程中，逃亡者会遇到 $5$ 个铁球而追逐者会遇到 $41$ 个铁球。

数据范围

对于 $100\%$ 的数据，有 $1\le n\le 10^5;0\le V\le 100;0\le F_i\le 10^9$​​。