신호등

면접 대비

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

요약

빨간불과 초록불 지속 시간이 주어진 n개의 신호등이 동시에 빨간불로 바뀐 뒤, 모든 신호등이 다시 초록불이 되는 가장 이른 시각을 구합니다.

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

문제

한 거리에 신호등 $n$ 개가 있다. 각 신호등은 빨간불이 $r$ 초, 초록불이 $g$ 초 동안 켜지기를 번갈아 반복한다. $r$ 과 $g$ 의 값은 신호등마다 다를 수 있다.

모든 신호등이 처음에는 초록불이었다. 그러다 모든 신호등이 같은 순간에 빨간불로 바뀌었다. 모든 신호등이 다시 초록불이 될 때까지 몇 초가 걸리는지 구하라.

입력

첫 줄에 신호등의 개수 $n$ 이 주어진다 ( $1 \le n \le 10$ ). 다음 $n$ 개의 줄에는 각각 정수 $r$ 과 $g$ 가 주어진다 ( $1 \le r, g \le 10$ ). $r$ 과 $g$ 는 이 신호등이 빨간불과 초록불을 각각 유지하는 시간(초)이다.

출력

모든 신호등이 다시 초록불이 되는 가장 이른 시각을 정수 하나로 출력한다. 그런 시각이 없으면 $-1$ 을 출력한다.

예제1

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