Delivery Guy

Time limit2sMemory limit64 MB

Summary

On a tree of N restaurants with demand A_i, maximize total delivered peppers in M time units, where each visit costs 1 to deliver and each edge costs 1 to traverse.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, DFS, Backtracking
Solved: No attempts yet

Problem

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.

Input

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$ )

Output

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

Hint

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.

Examples3

Example 1
Input
```
3 5
9 2 5
1 2
1 3
```
Expected output
```
14
```
Example 2
Input
```
4 5
1 1 1 2
1 2
2 3
3 4
```
Expected output
```
3
```
Example 3
Input
```
5 10
1 3 5 2 4
5 2
3 1
2 3
4 2
```
Expected output
```
15
```