AT_ddcc2020_final_b Hawker on Graph

[problemUrl]: https://atcoder.jp/contests/ddcc2020-final/tasks/ddcc2020_final_b $ 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 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ W $ $ S $ $ K $ $ u_1 $ $ v_1 $ $ w_1 $ $ : $ $ u_M $ $ v_M $ $ w_M $

$ 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) $ ### Sample Explanation 1 頂点を $ 1\ \rightarrow\ 2\ \rightarrow\ 3\ \rightarrow\ 1\ \rightarrow\ 2\ \rightarrow\ 5 $ と移動すれば、所持金は $ 8 $ 円となります。 ### Sample Explanation 2 どのように操作を行っても $ 4 $ 回の操作を完了することはできません。したがって $ -1 $ を出力します。