汤姆猫又在追逐杰瑞鼠了！杰瑞试图通过跑进鸽群来获得优势，因为在鸽群中汤姆更难追踪他。杰瑞恰好来到了卢布尔雅那的中央公园。公园里有 $n$ 座雕像，编号为 $1 \dots n$，它们之间由 $n-1$ 条互不相交的通道连接，使得通过这些通道可以从任意一座雕像到达另一座雕像。在每座雕像 $i$ 周围聚集着 $p_i$ 只鸽子。杰瑞的口袋里有 $v$ 个面包屑。如果他在当前所在的雕像处丢下一个面包屑，相邻雕像处的鸽子会立即飞到这座雕像来吃面包屑。结果，这座雕像及其相邻雕像处的当前鸽子数量 $p$ 会发生变化。

这一切按以下顺序发生：首先，杰瑞到达雕像 $i$ 并遇到 $p_i$ 只鸽子。然后，他丢下面包屑。他离开雕像。相邻雕像处的鸽子在杰瑞到达下一座雕像之前移动到雕像 $i$（因此它们不会计入他遇到的鸽子数量中）。

杰瑞可以从任意雕像进入公园，沿着一些通道奔跑（但从不重复使用同一条通道），然后从他想要的任何地方离开公园。在杰瑞离开公园后，汤姆将进入并沿着完全相同的路线行进。通过丢下最多 $v$ 个面包屑，杰瑞想要最大化汤姆在路线上遇到的鸽子数量与他自己遇到的鸽子数量之间的差值。注意，只有在杰瑞到达某座雕像之前就存在于该雕像处的鸽子才计入他遇到的鸽子总数。有关进一步解释，请参阅样例说明。

输入格式

第一行包含雕像数量 $n$ 和面包屑数量 $v$。第二行包含 $n$ 个用空格分隔的整数 $p_1 \dots p_n$。接下来的 $n-1$ 行描述了通道，每行包含一对数字 $a_i$ 和 $b_i$，表示雕像 $a_i$ 和 $b_i$ 之间有一条通道。

输出格式

仅输出一个数字，即汤姆遇到的鸽子数量与杰瑞遇到的鸽子数量之间的最大差值。

数据范围

• $1 \le n \le 10^5$
• $0 \le v \le 100$
• $0 \le p_i \le 10^9$

子任务

• 子任务 1（20 分）：$1 \le n \le 10$
• 子任务 2（20 分）：$1 \le n \le 1000$
• 子任务 3（30 分）：最优路线从雕像 1 开始。
• 子任务 4（30 分）：无附加限制。

样例

输入 1

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

输出 1

36

说明

一种可能的方案如下：杰瑞在雕像 6 进入公园。他在那里遇到了 5 只鸽子。他丢下一个面包屑。此时 $p_6$ 变为 27，$p_5 = p_7 = p_8 = p_9 = 0$。接下来他跑到雕像 7，遇到 0 只鸽子。他丢下第二个面包屑。此时 $p_7$ 变为 41，$p_2 = p_4 = p_6 = p_{10} = 0$。他离开公园。他总共遇到了 $5 + 0 = 5$ 只鸽子。汤姆沿着同样的路线行进，但遇到了 $p_6 + p_7 = 0 + 41 = 41$ 只鸽子。差值为 $41 - 5 = 36$。