問題文

パ研王国には N 個の町があり、 M 本の道がそれらを結んでいます。i 番目の道は町 A_i から町 B_i を一方通行に結んでいます。 また、 P 個の町には 1 つずつ展望台があり、町 C_i の展望台は標高 D_i の場所に設置されています。

ZRK君はこれからドライブに行く計画を立てています。彼は町 S の展望台を出発し、いくつかの道を移動して町 T の展望台でドライブを終えます。 同じ町や道を何度通過しても構いません。

ZRK君は、通過した町に展望台がある場合必ず立ち寄ります。 彼の嬉しさは最初 0 ですが、出発時以外である展望台 i に立ち寄った時、その直前に立ち寄った展望台 j との標高差の絶対値 |D_i - D_j| だけ嬉しさが増えます。

彼は、ドライブを終えた後の嬉しさが K 以上となるルートでドライブをしたいです。 この条件を満たすルートの長さの最小値がいくつになるか求めてください。

ただし、ルートの長さは、全ての道に対する「この道を何回通ったか」の値の合計値とします。例えば、頂点 3→5→2→4→3→5→4 というルートを辿った場合、ルートの長さは 6 となります。
もし嬉しさが K 以上となるルートが存在しない場合、代わりに -1 と出力して下さい。

制約

• 入力は全て整数である。
• 2 \leq N \leq 50
• 1 \leq M \leq N(N-1)
• 1 \leq P \leq N
• 1 \leq S, T \leq N
• 1 \leq K \leq 10^9
• 1 \leq A_i , B_i \leq N (1 \leq i \leq M)
• A_i \neq B_i (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) (i \neq j)
• 1 \leq C_i \leq N (1 \leq i \leq P)
• 1 \leq D_i \leq 10^5 (1 \leq i \leq P)
• C_i \neq C_j (i \neq j)
• C_i = S となる i, C_j = T となる j が存在する。

小課題

1. (300 点) K \leq 20 を満たす。
2. (700 点) 追加の制約はない。

入力例1

4 5 3
2 2 11
2 1
1 3
3 2
3 4
4 1
1 1
2 3
4 5

出力例1

6

入力例2

3 2 2
1 3 5
1 2
2 3
1 1
3 3

出力例2

-1

入力例3

6 7 4
1 6 14
1 2
2 3
3 4
4 5
5 1
6 1
2 6
1 1
3 2
5 7
6 4

出力例3

7