問題文

時は1634年、オランダでチューリップバブルが起こり始める時期だ。
美しいチューリップが次々生まれ、人々は新品種に夢中になりはじめその話は田舎の領主のもとにも到達したのだ。

領主はチューリップ畑を開こうとしているが、良い品種はとんでもない値段が付き始めている。
貴方は領主の名代としてチューリップ球根の代金を工面するために村を回って臨時税を取り立てることとなった。
時は金也。領主は一刻もはやく金をそろえて植え時の秋が終わる前にチューリップ畑を開こうとしている。貴方は最大の税収をもって刻限までに帰宅することを期待されている。

村から上がる税収と、ある村と村の間を街道を使って行き来するのにかかる時間、それと領主のもとに税収をもって戻ってくるまでの刻限が与えられる。

これ等のデータからあなたは最大の税収を持って帰ることとなる。貴方は領主の定めた刻限までに最大で一体いくらの税収を持って帰ることができるだろうか。

入力

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

村を点とし、街道を線とすると、村と街道は木構造をなしている。 村には、0～N-1までの番号が付けられており、村0が領主のいる村である。 貴方は村0から出発し刻限までに村0に帰らなくてはいけない。
一行目に村の数Nと刻限までの残り時間$M$がスペース区切りで与えられる。
$1\le N\le 200$
$1\le M\le 2000$

続く$N$行に村0～村N-1までの税収が村0番から順番に与えらえる。
$1\le U_i\le 10000000$
続く$N-1$行に村と村を繋ぐ街道のデータが与えられる。
$A_i$ $B_i$ $C_i$
村$A_i$と村$B_i$が街道でつながっており、$A_i$と$B_i$を移動するのに片道（どちらからどちらへ行くにも）で$C_i$時間かかる。
$0\le A_i,B_i<N$
$1\le C_i\le 1000$
与えられる数字はすべて整数と仮定してよい。
刻限ちょうどに帰還した場合も間に合ったとみなす。
刻限までなら他の村へ行くために村０を何度も通りすぎてもよい。
最大の税収$T$を一行に出力すること。

出力

$T$ 最後に改行してください。

サンプル

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