2012 End of the World

Time limit1sMemory limit128 MB

Summary

Given N, P, V, find the minimum total time to reduce N members to one opinion via recursively splitting into groups that each meet at cost k*P+V.

Level: Medium6 of 10
Topics: Math, Dynamic programming, Binary search
Solved: No attempts yet

Problem

In 2012, Earth is about to end. To protect it, the emergency council of the superpower Safari World has been called. The council has N members, and they must choose one final opinion.

If a direct meeting has k participants, it takes the following time.

Each participant explains their opinion to the others for P minutes.
After all presentations, the participants vote for the best opinion, and the vote takes V minutes.

Therefore, when k >= 2, a direct meeting takes k * P + V minutes. If there is only one participant, there is already only one opinion, so no time is needed.

To make the decision faster, the members may be divided into several groups. All groups meet at the same time and each group chooses one representative opinion. After every group has finished, only the people who gave those representative opinions meet again by the same rules. A group may also be divided into smaller groups recursively, and the process continues until one final opinion remains.

Given N, P, and V, find the minimum time needed to obtain one final opinion when the groups are chosen optimally.

Input

The first line contains three integers N, P, and V.

Output

Print the minimum time M needed for the council to obtain one final opinion.

Constraints

1 <= N <= 10^15
1 <= P, V <= 1 000

Hint

In the first visible test, the 9 members can be divided into 3 groups of 3. Each group meeting takes 4 minutes, and then the 3 representatives meet for another 4 minutes, for a total of 8 minutes.

Examples3

Example 1
Input
```
9 1 1
```
Expected output
```
8
```
Example 2
Input
```
6 1 2
```
Expected output
```
8
```
Example 3
Input
```
6 2 1
```
Expected output
```
12
```