問題文

N 頂点 M 辺の重み付き有向グラフ G があります。 G の頂点には 1, 2, \ldots, N、辺には 1, 2, \ldots, M と番号が振られています。 辺 i は頂点 u_i から頂点 v_i へ張られており、辺の重みは w_i です。 あなたは、G 上で次のようなゲームをします。

初めに、所持金 W 円を持って頂点 S 上に立つ。その後、以下の操作を K 回行う:

• 自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接続する頂点に移動する。
• このとき、選んだ辺の重みを w とすると、w が正ならば w 円得る。逆に w が負ならば |w| 円失う。また、所持金が負となることはない。すなわち、元の所持金を t 円とすると、移動後の所持金は \mathrm{max}(t+w, 0) 円である。

同じ辺を何度通ってもよく、通るたびに所持金が変化します。 K 回の操作を完了する前に、移動が不可能になる頂点に訪れては行けません。 また、ゲーム終了時はどの頂点に立っていても構いません。

このとき、ゲーム終了時の所持金は最大でいくらにできるかを求め、出力してください。 ただし、どのように操作を行っても K 回の操作を完了できない場合は、-1 を出力してください。

制約

• 2 \leq N \leq 200
• 0 \leq M \leq N (N-1)
• 0 \leq W \leq 10^{16}
• 1 \leq S \leq N
• 1 \leq K \leq 10^9
• 1 \leq u_i, v_i \leq N (1 \leq i \leq M)
• -10^7 \leq w_i \leq 10^7 (1 \leq i \leq M)
• u_i \neq v_i (1 \leq i \leq M)
• i \neq j ならば (u_i, v_i) \neq (u_j, v_j)

入力例 1

5 6 0 1 5
1 2 1
2 3 2
3 4 1
4 1 -1
3 1 -4
2 5 7

出力例 1

8

頂点を 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 と移動すれば、所持金は 8 円となります。

入力例 2

5 6 10 1 4
1 2 1
1 3 3
2 4 6
5 4 0
3 5 2
2 5 1

出力例 2

-1

どのように操作を行っても 4 回の操作を完了することはできません。したがって -1 を出力します。

入力例 3

2 2 0 2 1000000000
1 2 100000
2 1 100000

出力例 3

100000000000000