Guessing Game

Time limit1sMemory limit256 MB

Summary

Identify a hidden integer from 1 to n with adaptive subset questions where each NO costs a and each YES costs b while minimizing the worst-case total.

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

Problem

John and George play the following game. John picks one integer $x$ from the set $A_n = \{1, 2, 3, \ldots, n\}$ , and George has to find out which integer it is. The game runs in moves $1, 2, 3, \ldots$ . On move $k$ George picks a subset $B_k$ of $A_n$ , and John answers YES if $x$ belongs to $B_k$ and NO otherwise. For a NO answer George pays John $a$ euros, and for a YES answer he pays $b$ euros.

George hears each answer before he picks the next subset. Among all strategies that always identify $x$ , find the one whose largest possible total payment is smallest, and compute that payment.

Input

The first line contains three integers $n$ , $a$ , and $b$ , separated by spaces.

Output

Print one integer, the minimum amount of euros George has to pay.

Constraints

$1 < n < 10^{18}$
$0 < a, b < 1\,000$

Hint

For $n = 5$ , $a = 1$ , $b = 2$ George can find $x$ for 4 euros.

George first picks $B_1 = \{1, 2\}$ .

If John answers YES, George pays 2 euros and picks $B_2 = \{1\}$ . On another YES he pays 2 more euros and the game ends ( $x = 1$ ). On NO he pays 1 more euro and the game ends ( $x = 2$ ).
If John answers NO, George pays 1 euro and picks $B_2 = \{3\}$ . On YES he pays 2 more euros and the game ends ( $x = 3$ ). On NO he pays 1 more euro and picks $B_3 = \{4\}$ . On YES he pays 2 more euros and the game ends ( $x = 4$ ). On NO he pays 1 more euro and the game ends ( $x = 5$ ).

The most expensive outcomes are $x = 1$ and $x = 4$ , and both cost 4 euros.

Examples2

Example 1
Input
```
5 1 2
```
Expected output
```
4
```
Example 2
Input
```
2 1 1
```
Expected output
```
1
```