Traffic Lights

Interview

Time limit1sMemory limit2048 MB

Summary

Given n traffic lights with red and green durations that all turn red together, find the earliest time when every light is green again, or -1 if that never happens.

Level: Medium4 of 10
Topics: Simulation, Number theory
Solved: No attempts yet

Problem

A street has $n$ traffic lights. Each light alternates between $r$ seconds of red and $g$ seconds of green. The values of $r$ and $g$ can differ from light to light.

All the lights were green. Then all of them turned red at the same moment. Find how many seconds it takes until every light is green again.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10$ ), the number of traffic lights. Each of the next $n$ lines contains two integers $r$ and $g$ ( $1 \le r, g \le 10$ ), the number of seconds that light stays red and green.

Output

Output a single integer, the earliest time at which all the lights are green again. If this never happens, output $-1$ .

Examples1

Example 1
Input
```
3
2 4
3 1
6 1
```
Expected output
```
27
```