No.417 チューリップバブル

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 59
作問者 : horiesinitihoriesiniti / テスター : maruokamaruoka

2 ProblemId : 1207 / 出題時の順位表

問題文

時は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 \lt N$
$1 \le C_i \le 1000$
与えられる数字はすべて整数と仮定してよい。
刻限ちょうどに帰還した場合も間に合ったとみなす。
刻限までなら他の村へ行くために村0を何度も通りすぎてもよい。
最大の税収$T$を一行に出力すること。

出力

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

サンプル

サンプル1
入力
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

村0、村2、村3、村4を回れば53の税収を持って帰れる。 村0での徴収はタイム0で行える。

サンプル2
入力
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

村0、村2、村4、村6で徴収すれば63となる。

サンプル3
入力
2 50
10
50
0 1 50
出力
10

隣村へは往復で100かかるので間に合わない。 村0だけ徴収して終わりである。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。