Maximum Pepper Delivery on a Tree Road Network

Krešo has grown chili peppers and now must deliver them to N restaurants connected by N-1 roads forming a tree. The restaurants are numbered from 1 to N. Restaurant i requires exactly \(A_i\) chili peppers. Starting at restaurant 1, Krešo has a total of M time units. In one unit of time he can either travel from the current restaurant to an adjacent one or deliver the peppers to the current restaurant – which delivers exactly the required \(A_i\) peppers (each restaurant can be delivered to at most once). Krešo carries an unlimited supply of peppers. His route can traverse roads arbitrarily (possibly revisiting restaurants) but each action (move or delivery) costs one time unit.

Determine the maximum total amount of peppers Krešo can deliver within the given time M.

Note: It is not required to return to the starting restaurant after the route.

inputFormat

The input consists of:

• A line containing two integers \(N\) and \(M\) \( (1 \leq N \leq 10^5,\, 0 \leq M \leq 10^5)\) — the number of restaurants and the total available time units.
• A second line containing \(N\) integers \(A_1, A_2, \dots, A_N\) \( (1 \leq A_i \leq 10^9)\) representing the required amount of peppers at each restaurant.
• Then \(N-1\) lines follow, each containing two integers \(u\) and \(v\) meaning there is a road between restaurants \(u\) and \(v\).

You can assume that the restaurants form a connected tree.

outputFormat

Output a single integer: the maximum amount of peppers that can be delivered within M time units.

sample

3 5
3 2 1
1 2
2 3

6