A kangaroo is in a certain position *n* ≥ 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}.

**(30 points)**Solving all the inputs of instance.**(70 points)**Solving all the other inputs.

Public test cases

**Input**

1 200 200 10 1 100 10 100 1 1024 1 1 1024 1 5 1234567 3 43 0 0 0

**Output**

0 9 103 10 42 766

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++