AT_ddcc2020_final_b Hawker on Graph

给定一个包含 $N$ 个顶点和 $M$ 条边的有向加权图 $G$。图中的顶点编号为 $1, 2, \ldots, N$，边编号为 $1, 2, \ldots, M$。每条边 $i$ 从顶点 $u_i$ 连接到顶点 $v_i$，边的权值为 $w_i$。你将在图 $G$ 上进行如下游戏： 开始时，你站在顶点 $S$ 上，并拥有 $W$ 元钱。接下来需进行 $K$ 次操作： - 从你当前所在的顶点出发，选择一条边移动到其连接的顶点。 - 如果边的权重 $w$ 为正数，你将增加 $w$ 元；如果 $w$ 为负数，你将减少 $|w|$ 元。你的钱不能为负，即每次移动后的钱数为 $\max(t+w,\ 0)$，其中 $t$ 是移动前拥有的钱。 你可以多次经过同一条边，且每次经过都会改变你的钱数。注意，在进行 $K$ 次操作前，你不能到达无法继续移动的顶点。游戏结束时，你可以站在任意顶点上。 请计算游戏结束时你最多可以拥有多少钱。如果无论如何都无法进行完 $K$ 次操作，输出 $-1$。

输入格式如下： > $N$ $M$ $W$ $S$ $K$ $u_1$ $v_1$ $w_1$ $: \ldots : 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. 通过路径 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5$，可以最终获得 $8$ 元。 2. 在任何情况下都无法完成 $4$ 次操作，所以输出 $-1$。 **本翻译由 AI 自动生成**

### 制約 - $ 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 $ を出力します。