問題文

一列に並んだ無限個のマスから成るマス目があり、マスには左から順番に $1,2,3,…$ の番号がついています。

このマス目で暮らしている大魔術師のあなたは、現在マス $1$ にいて、後述の方法で移動を繰り返してマス $N$ へ行こうとしています。

あなたは $M$ 本の魔法の杖を所持しており、魔法の杖にはそれぞれ $1,2,…,M$ の番号がついています。あなたはこの魔法の杖を用いてのみマス目の移動が出来ます。

移動の方法は以下の通りです。

1. 壊れていない魔法の杖を $1$ つ選ぶ。選んだ魔法の杖を $i$ 番とする。
2. 魔法の杖 $i$ で小魔法か大魔法を選んで使う。
   • 小魔法を選んだ場合、あなたは今いるマス目から右にちょうど $a_i$ マス進む。魔法の杖 $i$ は壊れず、再度選ぶことができる。
   • 大魔法を選んだ場合、あなたは今いるマス目から右にちょうど $b_i$ マス進む。魔法の杖 $i$ は壊れ、再度選ぶことはできない。
3. 壊れていない魔法の杖があるなら1. に戻る。そうでないなら移動を諦める。

マス $1$ からマス $N$ まで移動するのに必要な魔法の使用回数を出力してください。どのような手順で移動しようともマス $N$ に到達できず移動を諦めてしまう場合は -1 を出力してください。

ただし、魔法の使用回数とは小魔法の使用回数と大魔法の使用回数の合計のこととします。

制約

• $2 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• $1 \leq a_i \leq 2000$ $(1 \leq i \leq M)$
• $1 \leq b_i \leq 2000$ $(1 \leq i \leq M)$

入力

入力はすべて整数である。

N M
a_1 a_2 ... a_M
b_1 b_2 ... b_M

出力

マス $1$ からマス $N$ まで移動するのに必要な魔法の使用回数を出力してください。どのような手順で移動しようともマス $N$ に到達できず移動を諦めてしまう場合は -1 を出力してください。

サンプル

20 2
2 4
1 6

5

次のような手順で移動を行うと $5$ 回の魔法使用でマス $N$ に到達できます。

• はじめ、マス $1$ にいる。
• 魔法の杖 $2$ で小魔法を使う。マス $5$ にいる。
• 魔法の杖 $1$ で大魔法を使う。魔法の杖 $1$ は壊れてまう。マス $6$ にいる。
• 魔法の杖 $2$ で小魔法を使う。マス $10$ にいる。
• 魔法の杖 $2$ で小魔法を使う。マス $14$ にいる。
• 魔法の杖 $2$ で大魔法を使う。魔法の杖 $2$ は壊れてまう。マス $20$ にいる。

2000 30
455 841 1518 870 430 1613 1664 432 1875 1903 1697 1431 1487 1836 772 1771 759 58 1147 102 360 1439 1314 555 1525 419 320 1798 1146 1764
153 1652 996 1605 616 1416 246 1512 1344 608 1033 1375 1807 1533 364 1315 1451 1577 1809 1153 1959 807 1091 1389 1365 1545 497 552 1686 369

3

2000 7
968 1609 1549 1393 1018 1231 313
141 1420 1474 564 478 1252 1822

-1