002 - すごろくの並び替え(Sort of Sugoroku)

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 8 /


TLE
1sec
MLE
64MB
得点
100

問題文

hoiくんは友達とすごろくゲームをすることになった。
hoiくん達が遊ぶすごろくゲームは始めは0マス目にいて、サイコロの目分進み、進んだ先のマス目に書かれている数字の分進む、その先のマス目の指示には従わない。
そうしてnマスから超えたらゴールとなる。
hoiくんは自分が出すサイコロの目をm回分予知したのでなるべく早くゴールできるよう、
すごろくのマス目を入れ替えたい
マス目を適切に入れ替えた場合の最短手数を出力してください。

入力

n m
a1 a2 a3 .... am
b1 b2 b3 .... bn

1 行目にマス目 n,予知した出目数m が与えられる。

2 行目にi回目に出る予定の出目 ai が与えられる。(1 ≦ i ≦ m)

3 行目にjマス目の指示bj が与えられる。(1 ≦ j ≦ n)

出力

適切にマス目を入れ替えた場合の最短手数を出力せよ。出力の最後に改行を入れること。 ただしm回サイコロを回してもゴールにたどり着けなかった場合"NA"と出力せよ

制約

全ての入出力ケースについて以下を満たす。

  • 1 ≦ n, m ≦ 105
  • 0 ≦ ai ≦ 100
  • 0 ≦ bi ≦ 100
  • 初期位置は0マス目でありn+1マス目以上がゴールである。
  • 一回目に振る出目は1以上である

入出力例

入力例1

8 6
3 4 2 5 6 7
2 0 2 1 0 1 1 0

出力例1

2

入力例2

12 4
1 2 2 1
0 0 2 0 1 0 1 0 0 1 0 2

出力例2

NA