숫자 놀이

면접 대비

시간 제한2초메모리 제한512 MB

요약

N을 P1, P2, P3로 나눈 나머지가 각각 X1, X2, X3가 되는 가장 작은 양의 정수 N을 10억 미만에서 찾고, 없으면 -1을 출력한다.

난이도: 보통10점 중 4점
유형: 정수론, 수학, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

준서는 얼마 전에 나머지 연산을 배웠다. 양의 정수 $N$ 을 양의 정수 $M$ 으로 나눈 나머지가 언제나 0 이상 $M-1$ 이하라는 사실이 신기해서, 준서는 혼자 하는 숫자 놀이를 만들었다.

준서는 먼저 양의 정수 $X_1$ , $X_2$ , $X_3$ 을 마음대로 고른다. 그다음 $P_1 > X_1$ , $P_2 > X_2$ , $P_3 > X_3$ 을 만족하도록 양의 정수 $P_1$ , $P_2$ , $P_3$ 을 고른다. 준서가 알고 싶은 값은 다음 세 조건을 모두 만족하는 가장 작은 양의 정수 $N$ 이다.

$N$ 을 $P_1$ 로 나눈 나머지가 $X_1$ 이다.
$N$ 을 $P_2$ 로 나눈 나머지가 $X_2$ 이다.
$N$ 을 $P_3$ 으로 나눈 나머지가 $X_3$ 이다.

준서가 고른 $P_1$ , $P_2$ , $P_3$ , $X_1$ , $X_2$ , $X_3$ 이 주어질 때 가장 작은 $N$ 을 찾는 프로그램을 작성하시오.

입력

공백으로 구분된 정수 여섯 개 $P_1$ , $P_2$ , $P_3$ , $X_1$ , $X_2$ , $X_3$ 이 순서대로 주어진다. 모든 수는 1 이상 300 이하의 정수다.

출력

가장 작은 양의 정수 $N$ 을 한 줄에 출력한다.

조건을 만족하는 1,000,000,000 미만의 양의 정수가 없으면 -1을 출력한다.

예제3

예제 1
입력
```
20 20 20 1 2 3
```
예상 출력
```
-1
```
예제 2
입력
```
2 3 5 1 1 1
```
예상 출력
```
1
```
예제 3
입력
```
2 4 8 1 2 3
```
예상 출력
```
-1
```