Problem D: Chinese remainder theorem

Problem D: Chinese remainder theorem

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 114  Solved: 20
[Submit][Status][Web Board]

Description

Let us choose k different positive integers a1, a2, …, ak. For some non-negative integer x, divide it by ai(1 <= i <= k), we can get k remainders r1, r2,…, rk. Now give you ai and ri, please find the minimum x. If such x does not exist, print -1.

Input

The first line will be the integer k.

Then k lines, each line will contain two integers ai, ri.

The numbers in the input file don’t exceed 264-1.

Output

The value problem required.

The result doesn’t exceed 264-1.

Sample Input

2
8 7
11 9

Sample Output

31

HINT

[Submit][Status]