Jumping kangaroo P76214

A kangaroo is in a certain position $n \ge 1$, and he wants to reach the position 1. Spending $x$ units of energy, the kangaroo can make a step to the position $n - 1$. If $n$ is an even number, spending $y$ units of energy, the kangaroo can jump to the position $n/2$.

Your task is to write a program that given the initial position $n$, the constant $x$ and the constant $y$, prints the minimal cost of energy in order to the kangaroo goes from $n$ to 1.

Input

The input is a sequence of at most 10000 lines, each one with $n<10^8$, $x<10^5$ and $y<10^5$ in this order, separated by spaces. All the numbers of the input are integers strictly positive. A special line with the zeros indicates the end of the input and must not be processed.

Output

For each line of the input, your program must print the minimal cost of going from $n$ to 1 making steps of cost $x$ and jumps of cost $y$. This number will always be less than $10^8$.

Score

• (30 points) Solving all the inputs of instance.

• (70 points) Solving all the other inputs.