问题描述

给定一个具有 $N$ 个顶点和 $M$ 条边的带权有向图 $G$。图 $G$ 的顶点编号为 $1, 2, \\ldots, N$，边编号为 $1, 2, \\ldots, M$。边 $i$ 是从顶点 $u_i$ 到顶点 $v_i$ 的有向边，边的权重为 $w_i$。你在图 $G$ 上进行以下游戏：

一开始，你站在顶点 $S$ 上，并持有 $W$ 元钱。然后，重复以下操作 $K$ 次：

• 选择从当前所在顶点出发的一条边，移动到它连接的顶点。
• 此时，假设选择的边的权重为 $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)$

输入

从标准输入中按以下格式给出输入。

$N$ $M$ $W$ $S$ $K$ $u_1$ $v_1$ $w_1$ $:$ $u_M$ $v_M$ $w_M$

输出

如果可以完成 $K$ 次操作，则输出游戏结束时所持金的最大值。如果无论如何操作都无法完成 $K$ 次操作，则输出 $\-1$。

示例 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