주기 매미

면접 대비

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

요약

주기가 c1, c2인 매미 두 종이 y년에 함께 나타났다면, 여러 쌍 중 어느 쌍이 다시 함께 나타나는 가장 이른 연도를 구한다. 각 쌍의 다음 등장 연도는 y + lcm(c1, c2)이다.

난이도: 쉬움10점 중 3점
유형: 수학, 정수론, 구현
정답자: 아직 제출이 없습니다

문제

수명 주기가 각각 $13$ 년과 $17$ 년인 두 종류의 주기 매미가 있다. 할아버지가 '92년에 두 종류를 동시에 보았다고 한다. 두 매미를 다시 동시에 보려면 몇 년을 기다려야 하는지 궁금해졌다. 다른 주기 매미 쌍들에 대해서도 마지막으로 관찰된 시점을 조사하여, 다음 동시 출현 시기를 알아내려고 한다.

여러 쌍의 매미와 각 쌍이 마지막으로 동시에 나타난 연도가 주어졌을 때, 그중 한 쌍이 다시 나타나는 가장 이른 연도를 구하여라.

입력

첫째 줄에 주기 매미 쌍의 수 $k$ ( $1 \le k \le 99$ )가 주어진다. 이어서 $k$ 개의 줄이 주어지며, 각 줄에는 세 정수 $y$ , $c_1$ , $c_2$ ( $1800 \le y \le 2021$ , $1 \le c_1, c_2 \le 99$ )가 주어진다. $y$ 는 해당 쌍이 마지막으로 관찰된 연도이고, $c_1$ 과 $c_2$ 는 각각 첫 번째 종과 두 번째 종의 주기 길이이다. $k$ 개의 쌍 중 어느 것도 $2022$ 년보다 먼저 다시 나타나지 않는다고 가정해도 된다.

출력

어떤 쌍이 다시 나타나는 가장 이른 연도를 출력한다.

예제2

예제 1
입력
```
3
1992 13 17
1992 14 18
2001 5 7
```
예상 출력
```
2036
```
예제 2
입력
```
2
2020 2 3
2019 3 4
```
예상 출력
```
2026
```