Delivery Guy

Since Krešo started growing chili peppers, N restaurants across Croatia want his peppers so their dishes get real heat. Orders piled up, so Krešo decided to deliver the peppers himself.

The restaurants are numbered 1 to N and are joined by $N - 1$ roads, so a trip between any two restaurants is possible. Krešo starts at restaurant 1. In one unit of time he either drives to an adjacent restaurant or delivers peppers to the restaurant he is standing at. Restaurant i needs $A_i$ peppers. A restaurant takes a delivery only once, and that single delivery hands over its whole requirement $A_i$.

Delivering is tiring, so Krešo spends M units of time in total on driving and delivering, then takes a break. Find the largest amount of peppers Krešo can deliver within that time. Assume he always carries an unlimited supply of peppers.

The first line contains two integers N and M, the number of restaurants and the time Krešo plans to spend on delivery. ($1 \le N, M \le 500$)

The second line contains N integers $A_i$, the amount of peppers restaurant i needs. ($1 \le A_i \le 10^6$, $1 \le i \le N$)

Each of the next $N - 1$ lines contains two integers U and V, meaning a road joins restaurant U and restaurant V. ($1 \le U, V \le N$, $U \ne V$)

Print on one line the largest amount of peppers Krešo can deliver within the given time.

Look at the first example. Krešo delivers peppers to restaurant 1 (one unit of time), drives to restaurant 3 (one unit of time), then delivers peppers to restaurant 3 (one unit of time). Two units of time are left, enough to reach restaurant 2 but one unit short of delivering there.