P5054 [COCI 2017/2018 #7] Dostavljač

自从 Krešo 开始种植辣椒以来，克罗地亚各地的 $N$ 家餐馆都对他的辣椒感兴趣，因此他们可以用真正的香料来丰富他们的菜肴。由于需求量很大，Krešo 决定开始作为辣椒的送货员。 餐馆用从 $1$ 到 $N$ 的数字表示，并且与 $N - 1$ 个道路相互连接，使得可以在任何两个餐馆之间旅行。Krešo 在 $1$ 号餐厅开始他的旅程。在一个单位的时间里，他可以开车到相邻的餐厅或将辣椒送到现在的餐馆。对于每家餐厅，我们都知道所需的辣椒数量 $A_i$。 由于交付货物很累，Krešo 决定在交付和旅行上花费总共 $M$ 个单位的时间，之后他计划休息一下。 确定 Krešo 在给定时间范围内可以提供的最大辣椒数量。你可以假设 Krešo 总是带有无限量的辣椒。

第一行输入包含两个整数 $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$ 之间的道路。

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

**Clarification of the first test case:** In the first step, Krešo will deliver the peppers to restaurant 1. In the second step, Krešo will travel to restaurant 3. In the third step, Krešo will deliver the peppers to restaurant 3. He is left with 2 units of time, in which he can drive to restaurant 2, but he lacks one unit of time to deliver the peppers to that restaurant.