問題文

\(N\)個の町があります。それぞれ\(1 \ldots N\)と番号がふられています。
それぞれの街は直接、道でつながっているものもあれば、つながってないものがあります。
それぞれの道は　町\(S_i\)から町\(T_i\)に行くのに \(Y_i\)円がかかり、\(M_i\) 単位時間 かかります。

あなたは \(1\) の町にいます。
\(N\) の都市に行きたいと思っています。
何個道や町を経由してもいいですが、あなたは今\(C\)円しか持っていません。

（つまり、通った道のコスト \(Yi\) の合計を\(C\)以下にしないといけない。）

その中で一番早く着く道を選べた時、合計の単位時間を答えてください。
この制約の中で辿りつけない場合 \(-1\)を返してください。

入力

\(N\)
\(C\)
\(V\)
\(S_1\ S_2\ S_3\ \dots\ S_V\)
\(T_1\ T_2\ T_3\ \dots\ T_V\)
\(Y_1\ Y_2\ Y_3\ \dots\ Y_V\)
\(M_1\ M_2\ M_3\ \dots\ M_V\)

\(1\)行目に、町の数を表す整数 \( N\ ( 2 \leq N \leq 50 ) \) が与えられる。
\(2\)行目に、手持ちのお金を表す整数 \( C\ ( 1 \leq C \leq 300 ) \) が与えられる。
\(3\)行目に、道の数を表す整数 \( V\ ( 1 \leq V \leq 1500 ) \) が与えられる。
\(4\)行目に、\(S_i\ ( 1 \leq S_i \leq N ) \)が\(V\)個スペース区切りで与えられる。
\(5\)行目に、\(T_i\ ( S_i \lt T_i \leq N ) \)が\(V\)個スペース区切りで与えられる。
\(6\)行目に、\(Y_i\ ( 1 \leq Y_i \leq C ) \)が\(V\)個スペース区切りで与えられる。
\(7\)行目に、\(M_i\ ( 1 \leq M_i \leq 1000 ) \)が\(V\)個スペース区切りで与えられる。

\(S_i, T_i, Y_i, M_i\) は それぞれ \(i\) インデックス で町 \(S_i\) \(\rightarrow\) 町\(T_i\) （有向グラフ）の移動に　コスト\(Y_i\)　がかかり、\(M_i\) 単位時間かかるという意味です。

町どうしを道でつないだ後にできるグラフは閉路（ループ）がないとし、番号的には　\(S_i \lt T_i\)となっているとする。
つまり、番号的に戻る経路（例えば町\(3\)から町\(1\)など）へは考えなくてもよい。
道の接続的に町\(N\)に辿りつけない場合もあります。
\(S_i \rightarrow T_i\)への経路が複数ある場合があります。

出力

\(1\)の町から\(N\)の町へ行く一番早く着く道を選べた時、合計の単位時間を答えてください。
この制約の中で辿りつけない場合 -1を返してください。
最後に改行してください。

サンプル

3
100
3
1 2 1
2 3 3
10 90 10
10 10 50

20

3
100
3
1 2 1
2 3 3
1 100 10
10 10 50

50

10
10
19
1 1 2 4 5 1 3 4 6 4 6 4 5 7 8 2 3 4 9
3 5 5 5 6 7 7 7 7 8 8 9 9 9 9 10 10 10 10
8 6 8 7 6 6 9 9 7 6 9 7 7 8 7 6 6 8 6
8 9 10 4 10 3 5 9 3 4 1 8 3 1 3 6 6 10 4

-1

2
1
2
1 1
2 2
1 2
100 10

100