ICPC Square

Time limit1sMemory limit2048 MB

Summary

Given N, D, and S, find the highest floor reachable from S by moving from floor x to a multiple y of x where y minus x is at most D.

Level: Medium6 of 10
Topics: Number theory, Dynamic programming, Math
Solved: No attempts yet

Problem

ICPC Square is a hotel provided by the ICPC Committee for the accommodation of the participants. It has $N$ floors, numbered from 1 to $N$ . The hotel has an unusual elevator. A person on floor $x$ can ride the elevator once to floor $y$ if and only if $y$ is a multiple of $x$ and $y - x ≤ D$ .

You are currently on floor $S$ . You can ride the elevator zero or more times. Find the highest floor you can reach.

Input

A single line contains three integers $N$ , $D$ , and $S$ ( $2 ≤ N ≤ 10^{12}$ ; $1 ≤ D ≤ N - 1$ ; $1 ≤ S ≤ N$ ).

Output

Print a single integer, the highest floor you can reach by riding the elevator zero or more times.

Examples2

Example 1
Input
```
64 35 3
```
Expected output
```
60
```
Example 2
Input
```
2024 2023 1273
```
Expected output
```
1273
```