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.util.*;

public class Main {
    IOS ios;
    public static void main(String[] args) throws Exception {
        (new Main()).main();
    }

    void main() throws Exception {
        //ios = new IOS("main.in","");
        ios = new IOS("","");
        run();
        ios.close();
    }

    void run() throws Exception {
        ios.get();
        int n = ios.Int();
        long x = ios.Long();
        long y = ios.Long();
        long[] a = new long[2 * n + 1];
        for (int i = 1; i <= n; ++i) {
            if (a[i] == 0) {
                a[i] = (long)1e17;
            }
            if (i % 2 == 0) {
                a[i] = Math.min(a[i], Math.min(a[i - 1] + x, a[i >> 1] + y));
            } else {
                a[i] = Math.min(a[i], a[i - 1] + x);
            }
            if (a[i + i] == 0) {
                a[i + i] = a[i] + y;
            }
            for (int j = i + i - 1; a[j] == 0; --j) {
                a[j] = a[j + 1] + x;
            }
        }
        ios.w(a[n] + "\n");
    }
}

class IOS {
    BufferedReader  inp;
    BufferedWriter  out;
    IOS(String Inp, String Out) throws Exception {
        inp = new BufferedReader(Inp != "" ? (new FileReader(Inp)) : (new InputStreamReader(System.in)));
        out = new BufferedWriter(Out != "" ? (new FileWriter(Out)) : (new OutputStreamWriter(System.out)));
    }
    void close() throws Exception {
        out.flush(); inp.close(); out.close();
    }
    StringTokenizer i;
    void    get() throws Exception {i = new StringTokenizer(str());}
    String  str() throws Exception {return inp.readLine();}
    int     Int() throws Exception {return Integer.parseInt(i.nextToken());}
    long    Long() throws Exception {return Long.parseLong(i.nextToken());}
    String  word() throws Exception {return i.nextToken();}
    void    w(String s) throws Exception {out.write(s);}

    long gcd(long u, long v) {
        long w = 0;
        while (u > 0) {
            w = u;
            u = v % u;
            v = w;
        }
        return v;
    }
}