# #P2891. Strange Way to Express Integers

# 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 *a*_{1}, *a*_{2}, …, *a _{k}*. For some non-negative

*m*, divide it by every

*a*(1 ≤

_{i}*i*≤

*k*) to find the remainder

*r*. If

_{i}*a*

_{1},

*a*

_{2}, …,

*a*are properly chosen, m can be determined, then the pairs (

_{k}*a*,

_{i}*r*) can be used to express

_{i}*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*a*,_{i}*r*(1 ≤_{i}*i*≤*k*).

## 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