Apricot

Time limit1sMemory limit1024 MB

Summary

With one lighter counterfeit coin among N, find the minimum worst-case cost in apricots to identify it, where balanced weighings cost R and unbalanced weighings cost U.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search, Math, Divide and conquer
Solved: No attempts yet

Problem

Long ago the Golden Horde collected tribute in gold coins every year. The famous Crimean khan Girey decided to cheat: while paying tribute with N gold coins, he slipped one counterfeit coin among them, a lighter one. This was reported to the treasurer of the Golden Horde. To find the fake, he decided to use magic scales powered by apricots.

Two piles of coins are placed on the pans of the magic scales. The scales determine whether the weights of the piles are equal or different. If the piles have different weights, the scales also indicate which pile is lighter. When the weights of both piles are equal, the scales require R apricot fruits, and when they differ, U fruits.

The treasurer, himself a lover of apricots, wants both to find the counterfeit coin and to save on apricots.

Given the number of coins N, with exactly one of them lighter than the others, write a program that reports the minimum number of apricots with which the counterfeit coin is guaranteed to be found.

Input

The input file contains three integers N, R and U on a single line (2 ≤ N ≤ 1 000 000, 1 ≤ R, U ≤ 1 000 000), where N is the number of coins, R is the number of apricot fruits spent when the weights of the coin piles are equal, and U is the number of apricot fruits spent when they differ. All numbers are separated by a space.

Output

The output file must contain a single number: the minimum number of apricots with which the counterfeit coin is guaranteed to be found.

Notes

This problem has three subtasks. The score for each subtask is awarded only if all tests in its group are passed.

Examples4

Example 1
Input
```
4 3 1
```
Expected output
```
2
```
Example 2
Input
```
3 3 1
```
Expected output
```
3
```
Example 3
Input
```
15 2 3
```
Expected output
```
8
```
Example 4
Input
```
10 2 1
```
Expected output
```
3
```