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.

Input Specification

The first line of input contains two integers $N$ and $M$ $(1\le N,M\le 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\le A_i\le {10}^6)$, the required amount of peppers for restaurants denoted with $i$ $(1\le i\le N)$.

Each of the following $N-1$ lines contains two integers $U$ and $V$ $(1\le U,V\le N,U\ne V)$ that represent the road between restaurants $U$ and $V$.

Output Specification

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

Sample Input 1

3 5
9 2 5
1 2
1 3

Sample Output 1

14

Explanation for Sample Output 1

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.

Sample Input 2

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

Sample Output 2

3

Sample Input 3

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

Sample Output 3

15