Can you Divide?

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

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

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

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

• を素因数分解した際の各素因数の指数は高々
• 入力される値はすべて整数である

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

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

6 3
6 100
2 40
3 50

90

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

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

-1

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