Tree Advertising

Azerbaijan has $N$ cities, numbered $1$ through $N$, connected by $N-1$ roads so that every city can be reached from every other city along a sequence of roads. The IOI will soon be held in the capital Baku (city $1$), and everyone in the country will drive from their home city to the capital to watch the competition.

You want to use this occasion to advertise your new, very clever competitive programming judge by putting up posters on many trees along various roads. If you put up posters along a road, everyone who travels along that road at some point during their trip from their home city to the capital will see the poster.

You have judged that it adds nothing if a person sees your posters more than once during their trip. Your judge is so impressive that everyone wants to use it after seeing the poster a single time! Each road has a cost for putting up posters on all trees along it, each city has a population, and you have a limited budget. If you put up posters optimally, what is the largest number of people who will see at least one poster during their trip to the capital?

The first line contains two integers: the number of cities $N$ ($1 \le N \le 2\,000$) and your budget in kronor $B$ ($1 \le B \le 30\,000$).

The second line contains the $N-1$ numbers $p_2, p_3, \dots, p_N$ ($0 \le p_i \le 30\,000$). $p_i$ is the number of people who live in city $i$.

The following $N-1$ lines describe all the roads in Azerbaijan. The $i$-th of these lines contains the integers $a_i, b_i$ ($1 \le a_i, b_i \le N$) and $c_i$ ($1 \le c_i \le B+1$), meaning that the $i$-th road runs between cities $a_i$ and $b_i$ and costs $c_i$ kronor to put up posters along.

It is guaranteed that all cities can be reached from each other using these roads.

Print a single number: the largest number of people who can see your posters, if you place them optimally.

In the first example, it is optimal to put up one poster on the road between city $1$ and city $6$, and one between city $2$ and city $3$. This costs $350 + 100$ (which fits within the budget of $500$), and makes the people in cities $3$, $4$, $5$, and $6$ see the advertisement, for a total of $1000 + 100 + 300 + 300 = 1700$ people.