Problem Description

PuraPrime is wondering if there exists an integer $ N $ that satisfies all the following conditions:

• $1 \leq N \leq 10^{18}$
• $ N $ does not contradict the given $ M $ pieces of information. The $ i $-th piece of information consists of a prime number $ P_i $ and a positive integer $ S_i $, denoted as the pair $ (P_i, S_i) $. This information indicates that $ N! $ is divisible by $ P_i^{S_i} $ but not by $ P_i^{S_i+1} $.

Help PuraPrime by finding one $ N $ that satisfies the conditions, or inform them that such an $ N $ does not exist.

Input Format

The input is given from the standard input in the following format:

$ M $ $ P_1 $ $ S_1 $ $ P_2 $ $ S_2 $ $\vdots$ $ P_M $ $ S_M $

Output Format

If there exists an $ N $ that satisfies the conditions in the problem statement, output one such $ N $. If multiple answers exist, any one of them will be considered correct.

Otherwise, if no such $ N $ exists that satisfies the conditions in the problem statement, output -1.

Sample Input and Output

Sample Input #1

2
2 3
5 1

Sample Output #1

5

Sample Input #2

3
2 4
5 1
3 5

Sample Output #2

-1

Notes/Hints

Constraints

• $1 \leq M \leq 10^5$
• $1 \leq P_i \leq 10^9$
• $1 \leq S_i \leq 10^{18}$
• $ P_i $ is a prime number
• All inputs are integers

Sample Explanation 1

$ 5! = 120 $ is divisible by $ 2^3 = 8 $ but not by $ 2^4 = 16 $. Similarly, it is divisible by $ 5^1 = 5 $ but not by $ 5^2 = 25 $. Therefore, $ 5 $ satisfies the conditions in the problem statement.

Sample Explanation 2

If there is no integer that satisfies the conditions, output -1. Original idea: primenumber_zz

见题面 Input 部分

见题面 Output 部分