0426 - みついちゃんとでーと

問題

井田くんに彼女ができた。 名前はみついちゃん。
井田くんとみついちゃんが「でーと」をする。

現在、井田くんとみついちゃんは家（場所番号を1とする）にいる。
みついちゃんは N 個の「でーと」スポットを知っている。
ある「でーと」スポット N_i は、1分滞在するごとに x だけみついちゃんのデレ度があがる。
ある「でーと」スポットに行くための道はいくつかある。その総数は M 本である。
M_j 番目の道は、2つの「でーと」スポット a , b をつなぎ、その移動に c 分かかる。
全ての道は a から b へ一方通行で移動する。 b から a には移動できない。
「でーと」には、いつまでも時間を割けるわけではない。二人はT分だけ「でーと」ができる。
そして、 T 分後には家に居ないと、親にしかられてしまう。つまり、 T 分時点で家に居る必要がある。

井田くんは、みついちゃんのデレ度をできるだけ高くして、さらにらぶらぶになりたい。
情報が与えられた時に、みついちゃんのデレ度の最大値を求めよ。

入力

N M T
x1 x2 ... xn
a1 b1 c1
a2 b2 c2
.    .    .
.    .    .
.    .    .
am bm cm

1 行目に「でーと」スポットの数 N 、道の数 M 、「でーと」できる時間 T が与えられる。

2 行目に i 番目の「でーと」スポットに1分滞在した際のみついちゃんのデレ度の上昇量 x_i が与えられる。

3 行目から m+2 行目まで、繋がれる「でーと」スポット a と b 、その移動時間 c が与えられる。

出力

みついちゃんのデレ度の最大値を出力せよ。出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• 2≦N≦10⁵,1≦M≦min(N(N−1),10⁵),1≦T≦10⁹
• 1≦x_i≦10⁵
• 1≦a_i,b_i≦N,a_i≠b_i,1≦c_i≦10⁵

制約

この問題には部分点が設定されている。

• 1≦N≦200

このテストケースを満たすデータセットに正解した場合、3点が与えられる。

追加制約のないデータセットに正解した場合、+7点して10点が与えられる。

入出力例

入力例1

2 2 5
1 3
1 2 2
2 1 1

出力例1

6

• 開始から 0 分の時点から 2 分かけて「でーと」スポット1 から「でーと」スポット2 に移動する。
• 開始から 2 分の時点から 2 分間、「でーと」スポット2 に滞在する。みついちゃんのデレ度は 6 になる。
• 開始から 4 分の時点から 1 分かけて「でーと」スポット2 から「でーと」スポット1 に移動する。
• 開始から 5 分の時点で「でーと」スポット1 にいる。
• これでみついちゃんのデレ度が最高でなおかつ家にちゃんと帰れる最適解となる。

入力例2

2 2 3
1 3
1 2 2
2 1 1

出力例2

3

• この場合、おうちで「でーと」するのが最適解であり、みついちゃんのデレ度は3になる。

入力例3

8 15 120
1 2 6 16 1 3 11 9
1 8 1
7 3 14
8 2 13
3 5 4
5 7 5
6 4 1
6 8 17
7 8 5
1 4 2
4 7 1
6 1 3
3 1 10
2 6 5
2 4 12
5 1 30

出力例3

1488

ひんと

max(),min()は使用しないほうがいい。経験者は語る。
解法はダイクストラ。