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