Counterfeit Coin Detection

You are given n coins, among which exactly one coin is counterfeit. The counterfeit coin has a different weight than the genuine coins. You want to find the counterfeit coin in the minimum worst‐case time.

The process is performed in rounds. In the i^th round, you currently have x_i coins. You partition these coins into several groups, each containing exactly k_i coins, and any remaining coins (if any) form an extra group. Before weighing, you must pick up each coin which takes a seconds per coin, so picking up x_i coins takes a\,x_i seconds. Then, you weigh each group; weighing each group takes b seconds. Since the number of groups is \(\lceil \frac{x_i}{k_i} \rceil\), the weighing step takes \(b \cdot \lceil \frac{x_i}{k_i} \rceil\) seconds.

After weighing all the groups, you will identify the group whose total weight is different (which must exist because there is exactly one counterfeit coin). In the worst‐case scenario, the abnormal coin is always in a group that contains exactly k_i coins (and not in the leftover group, if any). You then proceed to the next round with x_i+1 = k_i coins. The process continues until you are left with a single coin (x_m = 1), at which point you have found the counterfeit.

The total time cost over m rounds is given by the formula:

\[ f = \sum_{i=1}^{m}\Bigl(a\,x_i + b \cdot \Bigl\lceil \frac{x_i}{k_i} \Bigr\rceil\Bigr) \]

Your task is to determine the minimum worst‐case time required to find the counterfeit coin if you can optimally choose the group sizes \(k_i\) in each round. In other words, given the worst case (i.e. each round the abnormal group is always one of size k_i), what is the minimum time required to identify the fake?

inputFormat

The input consists of a single line containing three integers n, a, and b separated by spaces, where:

• n is the number of coins.
• a is the time in seconds to pick up one coin.
• b is the time in seconds to weigh one group of coins.

outputFormat

Output a single integer representing the minimum worst‐case time (in seconds) required to identify the counterfeit coin.

sample

1 1 1

0