Optimal Query Cost in a Number Guessing Game

In this problem, Iris secretly chooses an integer \( m \) from the set \( S = \{1, 2, \dots, n\} \). Beryl then asks a sequence of questions of the form "Is \( m \) an element of the subset \( A \)?" where \( A \subseteq S \). Iris answers truthfully. Every time Iris answers yes, Beryl pays her \( a \) units of money; if she answers no, Beryl pays her \( b \) units. It is guaranteed that \( a > b \).

Beryl’s goal is to determine Iris’s number with a sequence of questions while minimizing the worst-case total payment. Your task is to compute the minimum amount of money that Beryl must prepare so that, regardless of Iris's choice, there exists a strategy (i.e. a sequence of questions) guaranteeing that the total payment will not exceed this amount when she identifies \( m \). If \( n = 1 \), no questions are needed and the answer is 0.

The optimal strategy is based on dynamic programming: Let \( F(x) \) be the maximum number of distinct numbers that can be resolved with a fund of \( x \). According to the rules, if \( x < b \), no question can be asked and hence \( F(x) = 1 \) (we can only have one possibility). For \( x \ge b \), one can ask a question and based on the answer spend either \( a \) or \( b \) units, so the recurrence is given by \[ F(x) = F(x - a) + F(x - b) \quad \text{for} \quad x \ge b, \] (with the convention that \( F(y) = 0 \) for \( y < 0 \)).

Your task is to find the smallest non-negative integer \( x \) such that \( F(x) \ge n \).

inputFormat

The input consists of three positive integers separated by spaces:

• \( n \) \( (1 \le n \le \text{large}) \) is the total number of positive integers in the set \( S \).
• \( a \) and \( b \) (with \( a > b \)) represent the amounts Beryl pays when Iris answers "yes" and "no", respectively.

If \( n = 1 \), no questions are needed and the answer should be 0.

outputFormat

Output the minimum amount of money Beryl must prepare in order to guarantee determining Iris's number \( m \) regardless of her choice.

sample

1 3 2

0