AT_tkppc4_2_j ドライブ旅行

[problemUrl]: https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_j パ研王国には $ 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 $ と出力して下さい。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ P $ $ S $ $ T $ $ K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ ... $ A_M $ $ B_M $ $ C_1 $ $ D_1 $ $ C_2 $ $ D_2 $ ... $ C_P $ $ D_P $

条件を満たすルートの長さの最小値を出力してください。 もしそのようなルートが存在しない場合、代わりに $ -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 $ が存在する。 ### 小課題 この課題には $ 2 $ つの小課題があります。 1. (300 点) $ K\ \leq\ 20 $ を満たす。 2. (700 点) 追加の制約はない。