問題文

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

また,あなたは変数xxを持っており,それは11で初期化されています.

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

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

制約

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

入力

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

ddNN
a1a_1b1b_1
a2a_2b2b_2
\vdots
aNa_NbNb_N

出力

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

サンプル

入力1
6 3
6 100
2 40
3 50
出力1
90

11つめの整数である66100100円で買ってしまえば100100円で目標を達成することができます. 一方,22つめの整数である2233つめの整数である33を買うことで40+50=9040+50=90円で目標を達成することができます. 目標を達成するための費用はこれ以上小さくならないので9090を出力します.

入力2
998244353 5
2 1
3 1
4 1
5 1
6 1
出力2
-1

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

Submit


Go (1.21)