問題文

Dungeon Attack (Easy) と Dungeon Attack (Hard) は同じ問題で、制約だけが異なります。

Dungeon Attack (Easy) は $300$ 点、 Dungeon Attack (Hard) は $600$ 点で、両方解くと $900$ 点になります。

アナウンス

• 05/01 00:09: 入力の $|C_i|$ は $|S_i|$ の間違いだったため修正しました。
• 05/01 00:33: スタート地点とゴール地点が明記されていなかったため修正しました。
• 05/01 12:11: 問題文が曖昧だったため追記しました。

ストーリー

高橋くんはダンジョンに挑みます。

このダンジョンには制限時間があり、 $T$ 分以内に地点 $1$ にあるスタートから地点 $N$ にあるゴールにたどり着けば攻略成功となり、それまでに獲得したスコア分のお金をもらえます。

しかし、制限時間内にゴールにたどり着けなければ攻略失敗となり、それまでに稼いでいたスコアに関わらずお金はもらえません。

ダンジョン内部は迷路となっていて、 $N$ 個の地点があり $M$ 本の道があります。

$i$ 番目の道は地点 $A_i$ から $B_i$ への一方通行の道で、通るには $1$ 分かかります。 スコア $S_i$ が決まっていて、道を $1$ 回通るごとにもらえます。 このスコアは負のこともあります。

高橋くんはどの地点でも $0$ 分以上滞在することができます。

高橋くんが地点 $1$ からスタートするとき、最大でどれだけのスコアを稼いでゴール地点 $N$ に行くことができるか求めてください。

なお、ゴール地点にたどり着いても、制限時間内であれば他の頂点へ行くことができます。

ただし、一度ゴールにたどり着いても、ゴールにいない状態で制限時間が経過すると攻略失敗となります。

制約

• $1 \le N \le 200$
• $0 \le M \le N^2$
• $1 \le A_i, B_i \le N$
• $|S_i| \le 10^9$
• $0 \le T \le 10^9$
• 多重辺や自己ループは存在しない （ある頂点から出てある頂点に入る辺は高々 $1$ 本であり、両端が同じ頂点であるような辺は存在しない）
• 入力はすべて整数である

入力

出力

答えを $1$ 行に出力せよ。

入出力例

3 3 5
1 2 1
2 3 2
3 2 3

8

$1\to2\to3$ と進むことでスコア $3$ を稼いで $2$ 分でゴールすることができます。

しかし制限時間に余裕があるため、さらに $\to2\to3$ と進むとスコア $8$ を稼いで $4$ 分でゴールすることができます。

2 1 10000
1 2 -10

0

ゴールしても損しかしないため、制限時間まで待ったほうが得です。