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

@SuppressWarnings("unchecked")
public class P710E {

  class Trio implements Comparable<Trio> {
    int n, kx, ky;

    public Trio(int n, int kx, int ky) {
      this.n = n;
      this.kx = kx;
      this.ky = ky;
    }

    @Override
    public int compareTo(Trio t) {
      return ((n != t.n) ? (n - t.n) : ((kx != t.kx) ? (kx - t.kx) : (ky - t.ky)));
    }

    @Override
    public int hashCode() {
      return (n ^ kx ^ ky);
    }

    @Override
    public boolean equals(Object o) {
      Trio t = (Trio)o;
      return ((n == t.n) && (kx == t.kx) && (ky == t.ky));
    }
  }

  int n, x, y, kx = Integer.MAX_VALUE, ky = Integer.MAX_VALUE;
  Set<Trio> trio = new /*Tree*/HashSet();

  void trace(int n, int kx, int ky) {
    Trio t = new Trio(n, kx, ky);

    if (trio.contains(t) || (((long)kx * x + (long)ky * y) >= ((long)this.kx * x + (long)this.ky * y))) {
      return;
    }

    if (n == 0) {
      if (((long)kx * x + (long)ky * y) < ((long)this.kx * x + (long)this.ky * y)) {
        this.kx = kx;
        this.ky = ky;
      }

      return;
    }

    trio.add(t);

    if ((n & 0b1) == 0) {
      if (((long)(n / 2) * x) < y) {
        trace(n / 2, kx + n / 2, ky);
      } else {
        trace(n / 2, kx, ky + 1);
      }
    } else {
      trace(n - 1, kx + 1, ky);
      trace(n + 1, kx + 1, ky);
    }
  }

  public void run() throws Exception {
    int n = nextInt();
    x = nextInt();
    y = nextInt();

    trace(n, 0, 0);
    
    println((long)kx * x + (long)ky * y);
  }

  public static void main(String... args) throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedOutputStream(System.out));
    new P710E().run();
    br.close();
    pw.close();
    System.err.println("\n[Time : " + (System.currentTimeMillis() - startTime) + " ms]");
  }

  static long startTime = System.currentTimeMillis();
  static BufferedReader br;
  static PrintWriter pw;
  StringTokenizer stok;

  String nextToken() throws IOException {
    while (stok == null || !stok.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null) { return null; }
      stok = new StringTokenizer(s);
    }
    return stok.nextToken();
  }

  void print(byte b) { print("" + b); }
  void print(int i) { print("" + i); }
  void print(long l) { print("" + l); }
  void print(double d) { print("" + d); }
  void print(char c) { print("" + c); }
  void print(Object o) {
    if (o instanceof int[]) { print(Arrays.toString((int [])o));
    } else if (o instanceof long[]) { print(Arrays.toString((long [])o));
    } else if (o instanceof char[]) { print(Arrays.toString((char [])o));
    } else if (o instanceof byte[]) { print(Arrays.toString((byte [])o));
    } else if (o instanceof short[]) { print(Arrays.toString((short [])o));
    } else if (o instanceof boolean[]) { print(Arrays.toString((boolean [])o));
    } else if (o instanceof float[]) { print(Arrays.toString((float [])o));
    } else if (o instanceof double[]) { print(Arrays.toString((double [])o));
    } else if (o instanceof Object[]) { print(Arrays.toString((Object [])o));
    } else { print("" + o); }
  }
  void print(String s) { pw.print(s); }
  void println() { println(""); }
  void println(byte b) { println("" + b); }
  void println(int i) { println("" + i); }
  void println(long l) { println("" + l); }
  void println(double d) { println("" + d); }
  void println(char c) { println("" + c); }
  void println(Object o) { print(o); println(); }
  void println(String s) { pw.println(s); }
  int nextInt() throws IOException { return Integer.parseInt(nextToken()); }
  long nextLong() throws IOException { return Long.parseLong(nextToken()); }
  double nextDouble() throws IOException { return Double.parseDouble(nextToken()); }
  char nextChar() throws IOException { return (char) (br.read()); }
  String next() throws IOException { return nextToken(); }
  String nextLine() throws IOException { return br.readLine(); }
  int [] readInt(int size) throws IOException {
    int [] array = new int [size];
    for (int i = 0; i < size; i++) { array[i] = nextInt(); }
    return array;
  }
  long [] readLong(int size) throws IOException {
    long [] array = new long [size];
    for (int i = 0; i < size; i++) { array[i] = nextLong(); }
    return array;
  }
  double [] readDouble(int size) throws IOException {
    double [] array = new double [size];
    for (int i = 0; i < size; i++) { array[i] = nextDouble(); }
    return array;
  }
  String [] readLines(int size) throws IOException {
    String [] array = new String [size];
    for (int i = 0; i < size; i++) { array[i] = nextLine(); }
    return array;
  }

  int gcd(int a, int b) {
    return ((b > 0) ? gcd(b, a % b) : a);
  }
}