# Strange Way to Express Integers

## Description

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

Choose k different positive integers a1, a2, …, ak. For some non-negative m, divide it by every ai (1 ≤ ik) to find the remainder ri. If a1, a2, …, ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.

“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”

Since Elina is new to programming, this problem is too difficult for her. Can you help her?

## Input

The input contains multiple test cases. Each test cases consists of some lines.

• Line 1: Contains the integer k.
• Lines 2 ~ k + 1: Each contains a pair of integers ai, ri (1 ≤ ik).

## Output

Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one. If there are no possible values, output -1.

``````2
8 7
11 9``````
``31``

## Hint

All integers in the input and the output are non-negative and can be represented by 64-bit integral types.

## Source

POJ Monthly--2006.07.30

, Static