Uolevi has a new job. As the first task in the job, he got a positive integer number $x$ and he has to transform it into $0$. Uolevi can do two kinds of operations:

• Divide the number by $2$ and round down. This costs $a$ euros.
• Decrease the number by $1$. This costs $b$ euros.

Find the minimum cost to transform the number into $0$.

Input

The input contains three integers, $x$, $a$ and $b$.

Output

Output the minimum cost to transform the number into $0$.

Constraints

• $1 \le x \le 10^9$
• $1 \le a \le 10^9$
• $1 \le b \le 10^9$

Examples

Input:

3 5 3

Output:

8

Input:

5 10 1

Output:

5