Number Game

Interview

Time limit2sMemory limit512 MB

Summary

Find the smallest positive N under 1e9 satisfying N mod P1 = X1, N mod P2 = X2, N mod P3 = X3, else print -1.

Level: Medium4 of 10
Topics: Number theory, Math, Brute force, Implementation
Solved: No attempts yet

Problem

Junseo recently learned about the remainder operation. He found it interesting that the remainder of a positive integer $N$ divided by a positive integer $M$ is always between 0 and $M-1$ , so he invented a number game he plays alone.

Junseo first picks positive integers $X_1$ , $X_2$ , $X_3$ freely. He then picks positive integers $P_1$ , $P_2$ , $P_3$ so that $P_1 > X_1$ , $P_2 > X_2$ , and $P_3 > X_3$ . What Junseo wants to know is the smallest positive integer $N$ that satisfies all three conditions below.

$N$ divided by $P_1$ leaves remainder $X_1$ .
$N$ divided by $P_2$ leaves remainder $X_2$ .
$N$ divided by $P_3$ leaves remainder $X_3$ .

Given the $P_1$ , $P_2$ , $P_3$ , $X_1$ , $X_2$ , $X_3$ that Junseo picked, write a program that finds the smallest $N$ .

Input

Six integers $P_1$ , $P_2$ , $P_3$ , $X_1$ , $X_2$ , $X_3$ are given in that order, separated by spaces. Every number is an integer between 1 and 300.

Output

Print the smallest positive integer $N$ on one line.

If no positive integer below 1,000,000,000 satisfies the conditions, print -1.

Examples3

Example 1
Input
```
20 20 20 1 2 3
```
Expected output
```
-1
```
Example 2
Input
```
2 3 5 1 1 1
```
Expected output
```
1
```
Example 3
Input
```
2 4 8 1 2 3
```
Expected output
```
-1
```