Lately, you have been noticing that all the farm animals around you have been making noises at suspiciously regular intervals. This is definitely not normal, and you think they might be trying to tell you something. You hypothesise that when all the animals make noise at the same time, some significant event will happen. Given the time they will first make noise after a particular time, as well as the periodicity of them making noises thereafter, calculate when they will all sync up, or if it will never happen.

You should also notice that all the animals begin making noises at different times, and might not be in sync. For example, if two animals have a periodicity of two, it does not always mean they are in sync. If one first makes noise at time 1, and the other at time 0, they will never sync up, so you should output as such. That is the significance of the first noise time.

Input

The first line consists of a single integer ~n~ ~(1 \leq n \leq 1000)~, the number of animals you have observed.

The next ~n~ lines each contain two space-separated integers ~a_i~ ~(0 \leq a_i \leq 10^9)~ and ~m_i~ ~(1 \leq p_i \leq 10^6)~, the starting time and periodicity thereafter of the ~i~th animal.

Additionally, the lowest common multiple of all ~m_i~ is guaranteed to be less than or equal to ~2^62~.

Output

Output the soonest time in which all ~n~ animals will make noise at the same time. If they will never sync up, output ~-1~.

Example

Input 1

2
1 3
2 4

Output 1

10

In this small example, we can simply list out all the times and see when they first intersect. For animal ~1~, we can see that it will be a multiple of ~3~ offset by ~1~, so we have ~1,4,7,10,13,\dots~. The second animal will be a multiple of ~4~ starting at ~2~, so we have ~2,6,10,14,\dots~. It can be seen that they will both make noise at the same time when ~t=10~.

Input 2

3
0 2
1 4
0 5

Output 2

-1

It can be observed that the first two animals will never sync up. The first one makes noise at all even-numbered times, while the second makes noise at all multiples of ~4~ offset by ~1~ (such as ~1,5,9,13,17,21,25~). It can be seen that these are all odd-numbered, so they will never line up.

Input 3

3
1 2
2 3
3 5

Output 3

23

We will illustrate the sequence of noise-making times for each animal as follows:

• Animal 1: ~1,3,5,7,9,11,13,15,17,19,21,23\dots~
• Animal 2: ~2,5,8,11,14,17,20,23,\dots~
• Animal 3: ~3,8,13,18,23,\dots~

The soonest time on which all animals sync up is ~t=23~