Traffic Lights

시간 제한1초메모리 제한2048 MB

요약

모두 막 빨간불이 된 신호등 n개가 각각 r초 빨강, g초 초록을 반복할 때, 모든 신호등이 동시에 초록이 되는 가장 이른 시각을 구하거나 -1을 출력합니다.

난이도: 보통10점 중 4점
유형: 수학, 정수론, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

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.

입력

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

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

출력

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

예제1

예제 1
입력
```
3
2 4
3 1
6 1
```
예상 출력
```
27
```