Problem C
Traffic Lights

You are staring down a street with $n$ traffic lights. Each traffic light has been set to alternate its color between $r$ seconds of red and $g$ seconds of green based on the two duration parameters $r$ and $g$. These two parameters may vary across different traffic lights.

You saw that all the traffic lights had been green, but had just all turned red at the same time. You are wondering how many seconds it would take before the traffic lights are all green again.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 10$), the number of traffic lights.

The next $n$ lines each contain two integers $r$ and $g$ ($1 \le r, g \le 10$), giving the number of seconds that a traffic light stays red and green respectively.

Output

Output a single integer, the earliest time that the lights are all green again. If this will never happen, output $-1$.

3
2 4
3 1
6 1

27