Problem Description

There is a directed weighted graph $ G $ with $ N $ vertices and $ M $ edges. The vertices of $ G $ are numbered $1, 2, \ldots, N$, and the edges are numbered $1, 2, \ldots, M$. Edge $ i $ connects vertex $ u_i $ to vertex $ v_i $, and has a weight of $ w_i $. You will play the following game on $ G $:

Initially, you stand on vertex $ S $ with $ W $ yen (Japanese currency). Then, you perform the following operation $ K $ times:

• Choose one of the edges emanating from your current vertex and move to the vertex connected by that edge.
• If the chosen edge has a weight $ w $, you gain $ w $ yen if $ w $ is positive, and lose $ |w| $ yen if $ w $ is negative. Your money cannot become negative; that is, if your original amount of money is $ t $ yen, your money after moving becomes $\mathrm{max}(t+w, 0)$ yen.

You can traverse the same edge multiple times, and each time your money changes accordingly. You must not visit a vertex where it becomes impossible to move before completing $ K $ operations. Also, you can end the game standing on any vertex.

Determine the maximum amount of money you can have at the end of the game and output it. If it is impossible to complete $ K $ operations no matter how you perform them, output $ -1 $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

If it is possible to complete $ K $ operations, output the maximum amount of money at the end of the game. If it is impossible to complete $ K $ operations, output $ -1 $.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8

Sample Input #2

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

Sample Output #2

-1

Sample Input #3

2 2 0 2 1000000000
1 2 100000
2 1 100000

Sample Output #3

100000000000000

Notes/Hints

Constraints

• $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)$
• If $i \neq j$, then $(u_i, v_i) \neq (u_j, v_j)$

Sample Explanation 1

If you move through the vertices in the order $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5$, your money will be $ 8 $ yen.

Sample Explanation 2

No matter how you perform the operations, it is impossible to complete $ 4 $ operations. Therefore, output $ -1 $.

见题面 Input 部分

见题面 Output 部分