問題文

$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