Description

自从 Krešo 开始种植辣椒以来，克罗地亚各地的 $N$ 家餐馆都对他的辣椒感兴趣，因此他们可以用真正的香料来丰富他们的菜肴。由于需求量很大，Krešo 决定开始作为辣椒的送货员。

餐馆用从 $1$ 到 $N$ 的数字表示，并且与 $N - 1$ 个道路相互连接，使得可以在任何两个餐馆之间旅行。Krešo 在 $1$ 号餐厅开始他的旅程。在一个单位的时间里，他可以开车到相邻的餐厅或将辣椒送到现在的餐馆。对于每家餐厅，我们都知道所需的辣椒数量 $A_i$。

由于交付货物很累，Krešo 决定在交付和旅行上花费总共 $M$ 个单位的时间，之后他计划休息一下。

确定 Krešo 在给定时间范围内可以提供的最大辣椒数量。你可以假设 Krešo 总是带有无限量的辣椒。

Input Format

第一行输入包含两个整数 $N$ 和 $M$（$1 \le N, M \le 500$），餐馆数量和 Krešo 计划用于交付辣椒的时间。

第二行输入包含 $N$ 个整数 $A_i$（$1 \le A_i \le 10^6$），用 $i$ 表示的餐馆所需的辣椒数量（$1 \le i \le N$）。

以下 $N - 1$ 行中的每一行包含两个整数 $U$ 和 $V$（$1 \le U, V \le N$，$U \ne V$），其表示餐馆 $U$ 和 $V$ 之间的道路。

Output Format

您必须输出 Krešo 在给定时间范围内可以提供的最大量的辣椒。

3 5
9 2 5
1 2
1 3

14

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

3

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

15