SUSTech Online Judge

10561056 SUSTech Online Judge

Problem 1056 --Chinese remainder theorem

1056: 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 a₁, a₂, …, a_k. For some non-negative integer x, divide it by a_i(1 <= i <= k), we can get k remainders r₁, r₂,…, r_k. Now give you a_i and r_i, 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 a_i, r_i.

The numbers in the input file don’t exceed 2⁶⁴-1.

Output

The value problem required.

The result doesn’t exceed 2⁶⁴-1.

Sample Input

2
8 7
11 9

1056: Chinese remainder theorem

Description

Input

Output

Sample Input

Sample Output

HINT

Source