Problem: 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.

Examples

Input

8 1 1


Output

4


Input

8 1 10


Output

8

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;


/**
 * @author ramilagger
 */
public class Main {

    final static boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    public void solve() {
        int n = nextInt(),x = nextInt(), y = nextInt();
        long[] dp = new long[n + 1];
        dp[1] = x;
        for (int i = 2; i <= n; i++)
            dp[i] = Math.min(dp[i - 1] + x,dp[(i >>> 1) + i % 2] + y + (i % 2) * x);
        pw.println(dp[n]);
    }

    public void run() {
        start = System.currentTimeMillis();
        solve();
        if (!ONLINE_JUDGE) {
            long end = System.currentTimeMillis();
            System.err.println(end - start + " ms");
        }
        try {
            br.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        pw.close();
    }

    public Main() {

        try {
            br = (ONLINE_JUDGE) ? new BufferedReader(new InputStreamReader(System.in))
                    : new BufferedReader(new FileReader("in.txt"));

            pw = (ONLINE_JUDGE) ?
                    new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)))
                    : new PrintWriter(new BufferedWriter(new FileWriter("out.txt")));

        } catch (Exception e) {
            throw new RuntimeException();
        }

    }

    public static void main(String[] args) {
        new Main().run();
    }

    public String next() {
        try {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
        } catch (IOException e) {
            throw new RuntimeException();
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public BigInteger nextBigInteger() {
        return new BigInteger(next());
    }

    public String nextLine() {
        StringBuilder sb;
        try {
            while (st == null || !st.hasMoreTokens())
                return br.readLine();
            sb = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens())
                sb.append(" " + st.nextToken());
        } catch (IOException e) {
            throw new RuntimeException();
        }
        return sb.toString();
    }

    public int[] nextArray(int n) {
        int[] temp = new int[n];
        for (int i = 0; i < n; i++)
            temp[i] = nextInt();
        return temp;
    }

    public long[] nextLArray(int n) {
        long[] temp = new long[n];
        for (int i = 0; i < n; i++)
            temp[i] = nextLong();
        return temp;
    }

    long start;
    final BufferedReader br;
    final PrintWriter pw;
    StringTokenizer st;

}