_zscoder_ wants to generate an input file for some programming competition problem.
His input is a string consisting of _n_ letters 'a'. He is too lazy to write a generator so he will manually generate the input in a text editor.
Initially, the text editor is empty. It takes him _x_ seconds to insert or delete a letter 'a' from the text file and _y_ seconds to copy the contents of the entire text file, and duplicate it.
_zscoder_ wants to find the minimum amount of time needed for him to create the input file of exactly _n_ letters 'a'. Help him to determine the amount of time needed to generate the input.
## Input
The only line contains three integers _n_, _x_ and _y_ (1 ≤ _n_ ≤ 107, 1 ≤ _x_, _y_ ≤ 109) — the number of letters 'a' in the input file and the parameters from the problem statement.
## Output
Print the only integer _t_ — the minimum amount of time needed to generate the input file.
[samples]
_zscoder_ 想要为某个编程竞赛问题生成一个输入文件。
他的输入是一个由 #cf_span[n] 个字母 'a' 组成的字符串。他太懒了，不想写生成器，因此打算在文本编辑器中手动生成输入。
最初，文本编辑器是空的。在文本文件中插入或删除一个字母 'a' 需要 #cf_span[x] 秒，复制整个文本文件的内容并将其 duplicat（复制一份）需要 #cf_span[y] 秒。
_zscoder_ 希望找到生成恰好包含 #cf_span[n] 个字母 'a' 的输入文件所需的最少时间。请帮助他确定生成输入所需的最少时间。
输入仅包含一行，包含三个整数 #cf_span[n], #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ n ≤ 107], #cf_span[1 ≤ x, y ≤ 109]）——输入文件中字母 'a' 的数量以及问题描述中的参数。
## Input
输入仅包含一行，包含三个整数 #cf_span[n], #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ n ≤ 107], #cf_span[1 ≤ x, y ≤ 109]）——输入文件中字母 'a' 的数量以及问题描述中的参数。
## Output
请输出唯一的整数 #cf_span[t] —— 生成输入文件所需的最少时间。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the target number of 'a' characters.
Let $ x, y \in \mathbb{Z}^+ $ be the time costs for inserting/deleting one 'a' and copying the entire string, respectively.
**Constraints**
$ 1 \leq n \leq 10^7 $,
$ 1 \leq x, y \leq 10^9 $
**Objective**
Find the minimum time $ t $ to reach exactly $ n $ 'a's, starting from 0, using operations:
- Insert or delete one 'a': cost $ x $,
- Copy entire current string and append it (doubling): cost $ y $.
Let $ f(n) $ denote the minimum time to produce $ n $ 'a's. Then:
$$
f(0) = 0
$$
$$
f(n) = \min\left(
x \cdot n,\
\min_{\substack{1 \leq k < n \\ k \mid n}} \left\{ f(k) + y + f\left(\frac{n}{k} - 1\right) \cdot x \right\},\
\min_{\substack{1 \leq k \leq n}} \left\{ f(k) + y + f(n - k) \right\}
\right)
$$
Alternatively, via dynamic programming with state transitions:
$$
f(n) = \min \left( f(n-1) + x,\ \min_{\substack{d \mid n \\ d < n}} \left\{ f(d) + y + f\left(\frac{n}{d}\right) - x \right\} \right)
$$
But more practically, for $ n \geq 1 $:
$$
f(n) = \min_{k=1}^{n} \left\{ f(k) + y + f(n - k) \right\} \quad \text{(if doubling from } k \text{ to } 2k \leq n\text{)}
$$
Better formulation:
Let $ f(n) $ be minimal time to generate $ n $ 'a's. Then:
$$
f(n) = \min \left( n \cdot x,\ \min_{\substack{1 \leq d \leq \lfloor n/2 \rfloor}} \left\{ f(d) + y + f(n - d) \right\},\ \min_{\substack{d \mid n \\ d < n}} \left\{ f(d) + y + (n/d - 1) \cdot x \right\} \right)
$$
**Optimal formulation (standard solution):**
$$
f(n) = \min_{k=1}^{n} \left\{ f(k) + y + f(n - k) \right\} \quad \text{(general case)}
$$
But efficient recurrence:
$$
f(n) = \min \left( n \cdot x,\ \min_{\substack{d \mid n \\ d < n}} \left\{ f(d) + y + \left(\frac{n}{d} - 1\right) \cdot x \right\},\ \min_{\substack{1 \leq d < n}} \left\{ f(d) + y + f(n - d) \right\} \right)
$$
**Standard known solution (simplified):**
$$
f(n) = \min \left( n \cdot x,\ \min_{\substack{1 \leq d \leq n-1}} \left\{ f(d) + y + f(n - d) \right\},\ \min_{\substack{d \mid n,\ d \geq 2}} \left\{ f\left(\frac{n}{d}\right) + y + (d - 1) \cdot x \right\} \right)
$$
**Final concise formal statement:**
Let $ f(n) $ be the minimum time to generate $ n $ 'a's.
Then:
$$
f(0) = 0
$$
$$
f(n) = \min \left( n \cdot x,\ \min_{\substack{1 \leq d < n}} \left\{ f(d) + y + f(n - d) \right\},\ \min_{\substack{d \mid n,\ d > 1}} \left\{ f\left(\frac{n}{d}\right) + y + (d - 1) \cdot x \right\} \right)
$$
for $ n \geq 1 $.
**Objective:** Compute $ f(n) $.