注

コンテスト終了後にtwitterでkotatsugame_tさんより問題文の書き方に関する以下のご指摘をいただき^[1]、henkoudekimasuさんよりコンテスト終了後でも修正すべきとのご示唆をいただきました^[2]のでご指摘に沿うように修正いたしました：

• 競技プログラミングの問題文においてはmodの表記に原則 $[\textrm{mod} \ast]$ を使うべきでなく$\pmod{\ast}$ を使うべきである。
• 競技プログラミングの問題文においては数列の成分の表記に原則 $[ \ ]$ を使うべきでなくsubscriptを使うべきである。
• 競技プログラミングの問題文においては原則 $[ \ ]$ を $2$ 種類の用法で用いるべきではない。

より正確なご指摘・ご示唆の内容はページ下部の出典からご確認いただけます。

この度は競技プログラミングの慣習を知らずに不適切な問題文を記載してしまい参加者の皆様に不快な思いをさせてしまったことを心からお詫び申し上げます。

ついでに読みやすさも改善させるために文言を多少変えました。問題の内容自体に変更はございません。

問題文

入力に非負整数 $N$ と正整数 $M$ と長さ $M$ の正整数列 $B$ と長さ $M$ の整数列 $C$ が与えられます。

数列 $a$ とその長さ未満の非負整数 $m$ に対し、$a_m$ で $a$ の $1+m$ 個目の成分を表すことにします。すなわち省略記号 $\ldots$ を用いると $a$ は $(a_0,a_1,\ldots)$ と表されます。

$N$ 以下の非負整数 $n$ であって $M$ 未満の任意の非負整数 $m$ に対し $n \equiv C_m \pmod{B_m}$ を満たすものが存在するか否かを判定し、存在する場合はその最小値を求めてください。

入力

• $1$ 行目に $N$ が与えられます。
• $2$ 行目に $M$ が与えられます。
• $M$ 未満の各非負整数 $m$ に対し、$3 + m$ 行目に $B_m, C_m$ が半角空白区切りで与えられます。

制約

入力は以下の制約を満たします：

• $N$ は $10^5$ 以下の非負整数
• $M$ は $10^5$ 以下の正整数
• $M$ 未満の任意の非負整数 $m$ に対し、$B_m$ は $10^5$ 以下の正整数
• $M$ 未満の任意の非負整数 $m$ に対し、$C_m$ は $-10^5$ 以上 $10^5$ 以下の整数

出力

$N$ 以下の非負整数 $n$ であって $M$ 未満の任意の非負整数 $m$ に対し $n \equiv C_m \pmod{B_m}$ を満たすものが存在する場合はその最小値を $1$ 行に出力し、存在しない場合はNaNと出力してください。

最後に改行してください。

サンプル

10
1
1 2

0

100
2
6 3
4 2

NaN

1000
3
3 8
5 4
7 -8

104

出典

注に記載させていただいたご指摘内容の出典です。

1. kotatsugame_tさんのtweet
2. henkoudekimasuさんのtweet