A. Romantic date
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Rinat and Laysan are two snow leopards. Rinat has long wanted to ask Laysan out on a date. However, finding a suitable time for them to meet turns out to be not so easy: both of them have very unusual schedules.

Starting at time $$$0$$$, Rinat is free for the first $$$a$$$ seconds, busy for the next $$$a$$$ seconds, then free again for $$$a$$$ seconds, and so on.

Laysan's schedule is the opposite: she is busy for the first $$$b$$$ seconds, free for the next $$$b$$$ seconds, then busy again for $$$b$$$ seconds, and so on.

To ask Laysan out on a date, Rinat needs to find a time when they are both free for at least one full second.

Rinat is willing to wait until time $$$T$$$.

Find the minimum integer $$$t$$$ ($$$0 \le t \le T$$$) such that Rinat and Laysan are both free throughout the entire interval $$$[t,t+1)$$$, that is, from time $$$t$$$ inclusive to time $$$t+1$$$ exclusive.

If no such time exists, output $$$-1$$$.

Input

The first line contains three integers $$$a$$$, $$$b$$$, and $$$T$$$ ($$$1 \le a,b \le 10^{18}$$$, $$$0 \le T \le 10^{18}$$$).

Output

Output the minimum integer $$$t$$$ such that during the entire time interval $$$[t,t+1)$$$ Rinat and Laysan are both free.

If no such $$$t$$$ exists, output $$$-1$$$.

Scoring

The tests for this problem consist of seven groups. Points for each group are awarded only if all tests of the group, all tests required for it, and the tests from the statement are passed.

GroupPoints Additional constraints Required groups
115$$$T \le 10^6$$$–
215$$$a, b \le 10^3$$$–
310$$$blt; a$$$–
415$$$blt; 2a$$$3
515$$$blt; 1\,000\,001 \cdot a$$$2–4
610$$$b$$$ is divisible by $$$a$$$–
720No additional constraints1–6
Examples
Input
5 3 10
Output
3
Input
3 5 10
Output
6
Input
3 8 5
Output
-1
Note

In the first example, Rinat is free during the first $$$5$$$ seconds, that is, on the interval $$$[0,5)$$$, then busy on $$$[5,10)$$$. Laysan, on the contrary, is busy on $$$[0,3)$$$ and free on $$$[3,6)$$$. Therefore, the first time they are both free is on the interval $$$[3,5)$$$, and the minimum suitable moment is $$$3$$$.

In the second example, Laysan is free on $$$[5,10)$$$. At moment $$$5$$$, Rinat is still busy, since his busy interval is $$$[3,6)$$$. Starting from moment $$$6$$$, he is free again, so the answer is $$$6$$$.

In the third example, there is no suitable moment before $$$T=5$$$: Laysan becomes free only at moment $$$8$$$. Therefore, the answer is $$$-1$$$.