問題文

プラプライムくんは、以下の条件をすべて満たす整数 N が存在するか気になっています。

• 1 \leq N \leq 10^{18}
• N は与えられる M 個の情報に矛盾しない。i 個目の情報は素数 P_i と正整数 S_i の組 (P_i,S_i) からなり、N! は P_i^{S_i} で割り切れるが、P_i^{S_i+1} で割り切れないことを表す。

プラプライムくんのために条件を満たす N を 1 つ見つけてあげるか、あるいはそのような N が存在しないことを教えてあげてください。

制約

• 1 \leq M \leq 10^5
• 1 \leq P_i \leq 10^9
• 1 \leq S_i \leq 10^{18}
• P_i は素数
• 入力は全て整数

入力例 1

2
2 3
5 1

出力例 1

5

5! = 120 は 2^3 = 8 で割り切れますが、2^4 = 16 では割り切れません。また、同様に 5^1 = 5 で割り切れますが、5^2 = 25 では割り切れません。

よって 5 は問題文中の条件を満たします。

入力例 2

3
2 4
5 1
3 5

出力例 2

-1

条件を満たす整数が存在しない場合は、-1 を出力してください。

原案: primenumber_zz