問題文

正整数$d$が与えられます．この$d$を素因数分解した際の各素因数の指数は高々$1$であることがわかっています．

また，あなたは変数$x$を持っており，それは$1$で初期化されています．

あなたは今富山県にある整数を売っているお店を訪れており，そこには$N$個の整数が売られています． $i$個目の整数は$a_i$でその値段は$b_i$円です．あなたはここで好きなだけ整数を買うことができ，買った整数を$x$にかけます． より正確に述べると，$b_i$円支払って$i$個目の整数を購入し，$x\leftarrow x\times a_i$と更新します．

あなたはいくつかの整数を買ったあと$x$が$d$で割り切れるようにしたいと思いました．これを達成するための費用の最小値を求めてください． また，達成することができない場合はそのことを報告してください．

制約

• $1 \leq d \leq 10^9$
• $1 \leq N \leq 10^3$
• $1 \leq a_i,b_i \leq 10^9$
• $d$を素因数分解した際の各素因数の指数は高々$1$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます．

出力

$x$が$d$で割り切れるようにするための費用の最小値を答えよ， どれだけ整数を買っても目標を達成することができない場合は-1を出力せよ．

サンプル

6 3
6 100
2 40
3 50

90

$1$つめの整数である$6$を$100$円で買ってしまえば$100$円で目標を達成することができます． 一方，$2$つめの整数である$2$と$3$つめの整数である$3$を買うことで$40+50=90$円で目標を達成することができます． 目標を達成するための費用はこれ以上小さくならないので$90$を出力します．

998244353 5
2 1
3 1
4 1
5 1
6 1

-1

店にある整数をすべて買っても$x$を$d$で割り切れるようにすることができません． よって$-1$を出力します．