Problem Statement

The year is 1634, the time when the tulip bubble is beginning to take hold in the Netherlands.
Beautiful tulips are being created one after another, people are becoming infatuated with the new varieties, and the talk has reached even a lord in the countryside.

The lord intends to open a tulip field, but good varieties are starting to fetch outrageous prices.
As the lord's deputy, you are to travel around the villages collecting a special tax in order to raise the money for the tulip bulbs.
Time is money. The lord wants to gather the money as soon as possible and open the tulip field before autumn, the planting season, ends. You are expected to return home by the deadline with the maximum tax revenue.

You are given the tax revenue obtainable from each village, the time it takes to travel between certain villages along the highways, and the deadline for returning to the lord with the tax revenue.

From these data, you are to bring back the maximum tax revenue. What is the maximum tax revenue you can bring back by the deadline set by the lord?

Input

$N$ $M$
$U_0$
$\dots$
$U_{N-1}$
$A_1$ $B_1$ $C_1$
$\dots$
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$

Regarding villages as vertices and highways as edges, the villages and highways form a tree. The villages are numbered from 0 to N-1, and village 0 is the village where the lord lives. You must depart from village 0 and return to village 0 by the deadline.
The first line contains the number of villages N and the time remaining until the deadline $M$, separated by a space.
$1\le N \le 200$
$1\le M \le 2000$

The following $N$ lines give the tax revenues of village 0 through village N-1, in order starting from village 0.
$1\le U_i \le 10000000$
The following $N-1$ lines give the data of the highways connecting the villages.
$A_i$ $B_i$ $C_i$
Village $A_i$ and village $B_i$ are connected by a highway, and traveling between $A_i$ and $B_i$ takes $C_i$ time one way (in either direction).
$0 \le A_i,B_i \lt N$
$1 \le C_i \le 1000$
You may assume that all given numbers are integers.
Returning exactly at the deadline also counts as being in time.
As long as it is before the deadline, you may pass through village 0 any number of times in order to go to other villages.
Output the maximum tax revenue $T$ on one line.

Output

$T$ Print a newline at the end.

Sample

7 100
2
50
20
20
11
5
5
0 1 50
0 2 20
2 3 20
2 4 10
4 5 5
4 6 5

53

7 100
2
50
20
20
11
10
30
0 1 50
0 2 20
2 3 20
2 4 11
4 5 9
4 6 11

63

2 50
10
50
0 1 50

10