Guessing Game

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.

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

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

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

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.