Two-Bill Purchase

Time limit0.5sMemory limit128 MB

Summary

Given a target amount D and two bill denominations P and Q, find the minimum total payment at least D achievable using nonnegative counts of each bill.

Level: Hard8 of 10
Topics: Number theory, Math, Greedy, Recursion
Solved: No attempts yet

Problem

You can pay using only two kinds of bills: bills worth P and bills worth Q. You may use as many bills of each kind as needed.

An item costs D. To buy it, the amount paid must be at least D. Find the smallest amount that can be paid.

Input

The first line contains D, P, and Q separated by spaces. Each value is a natural number not greater than 10^9.

Output

Print the minimum amount that can be paid to buy the item.

Examples5

Example 1
Input
```
17 7 13
```
Expected output
```
20
```
Example 2
Input
```
21 7 13
```
Expected output
```
21
```
Example 3
Input
```
17 7 9
```
Expected output
```
18
```
Example 4
Input
```
37 9 17
```
Expected output
```
43
```
Example 5
Input
```
287341 2345 7253
```
Expected output
```
287398
```