Fruit Feast

Interview

Time limit2sMemory limit512 MB

Summary

Eat unlimited fruits that add A or B without passing T, using at most one halving, to reach the largest fullness.

Level: Medium5 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Bessie has broken into Farmer John's house again. In the kitchen she found a pile of lemons and a pile of oranges, and there are so many of each that you can treat the supply as unlimited. She plans to eat as much as she can.

Bessie's fullness can never go above $T$ . Eating one orange raises her fullness by $A$ , and eating one lemon raises it by $B$ . She refuses any fruit that would push her fullness past $T$ .

Bessie can also drink water at most one time. Drinking water immediately cuts her fullness in half, rounded down.

Find the largest fullness Bessie can reach.

Input

The first and only line contains three integers $T$ , $A$ , and $B$ , separated by spaces. ( $1 \le T \le 5\,000\,000$ , $1 \le A, B \le T$ )

Output

Print the largest fullness Bessie can reach, on one line.

Examples2

Example 1
Input
```
8 5 6
```
Expected output
```
8
```
Example 2
Input
```
17 6 6
```
Expected output
```
15
```