题目描述

Ever since Krešo started growing chili peppers, N restaurants all over Croatia showed interest in his peppers so they could enrich their dishes with real spice. Because of high demand, Krešo decided to start working as a delivery guy of chili peppers.

The restaurants are denoted with numbers from 1 to N and are mutually connected with N - 1 roads such that traveling between any two restaurants is possible. Krešo begins his journey in the restaurant denoted with 1. In one unit of time, he can either drive to the adjacent restaurant or deliver the peppers to the current restaurant. For each restaurant, we know the required amount of peppers $A_i$.

Since delivering goods is tiring, Krešo decided to spend a total of M units of time on delivery and travel, after which he plans to take a break.

Determine the maximal amount of peppers Krešo can deliver in the given timeframe. You can assume that Krešo always carries an unlimited supply of peppers.

输入格式

The first line of input contains two integers N and M (1 ≤ N, M ≤ 500), the number of restaurants and the time Krešo plans to spend delivering peppers.

The second line of input contains N integers $A_i$ (1 ≤ $A_i$ ≤ $10^6$ ), the required amount of peppers for restaurants denoted with i (1 ≤ i ≤ N).

Each of the following N - 1 lines contains two integers U and V (1 ≤ U, V ≤ N, U ≠ V) that represent the road between restaurants U and V.

输出格式

You must output the maximal amount of peppers Krešo can deliver in the given timeframe.

题目大意

自从 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 在给定时间范围内可以提供的最大量的辣椒。

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

提示

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.