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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Codeforces{	

	public static void main(String[] args) throws IOException{	
		Scan scan = new Scan();
	       int n = scan.nextInt();
	       int x = scan.nextInt();
	       int y = scan.nextInt();
	       long[] time = new long[n + 1];
	       time[0] = 0;
	       time[1] = x;	       
	       for(int i = 2; i <= n; i++){    	   
	    	   long puttime = time[i - 1] + x;
	    	   long duptime = time[(i + 1) / 2] + y;
	    	   if((i & 1) != 0) duptime += x;
	    	   time[i] = Math.min(puttime, duptime);
	       }
	       System.out.println(time[n]);
	}
			
	public static class Scan{		
		BufferedReader br;	
		String[] s;
		String str;
		int strIndex;
		int index;
		public Scan(){
			br = new BufferedReader(new InputStreamReader(System.in));
			index = 0;
			s = new String[0];
			str = "a";
			strIndex = 1;
		}
		public String nextLine() throws IOException{
			return br.readLine();
		}
		public char nextChar() throws IOException{
			if(strIndex == str.length()){
				str = br.readLine();
				strIndex = 0;
			}
			strIndex++;
			return str.charAt(strIndex - 1);
		}
		public char[] nextCharArray() throws IOException{
			str = br.readLine();
			strIndex = str.length();
			return str.toCharArray();
		}
		public int[] nextIntArray() throws IOException{
			s = br.readLine().split(" ");
			int[] result = new int[s.length];
			for(int i = 0; i < s.length; i++) result[i] = Integer.parseInt(s[i]);
			index = s.length;
			return result;
		}
		public long[] nextLongArray() throws IOException{
			s = br.readLine().split(" ");
			long[] result = new long[s.length];
			for(int i = 0; i < s.length; i++) result[i] = Long.parseLong(s[i]);
			index = s.length;
			return result;
		}
		public double[] nextDoubleArray() throws IOException{
			s = br.readLine().split(" ");
			double[] result = new double[s.length];
			for(int i = 0; i < s.length; i++) result[i] = Double.parseDouble(s[i]);
			index = s.length;
			return result;
		}
		public int nextInt() throws IOException{
			if(index == s.length){
				s = br.readLine().split(" ");
				index = 0;
			}
			index++;
			return Integer.parseInt(s[index - 1]);			
		}
		public long nextLong() throws IOException{
			if(index == s.length){
				s = br.readLine().split(" ");
				index = 0;
			}
			index++;
			return Long.parseLong(s[index - 1]);			
		}
		public double nextDouble() throws IOException{
			if(index == s.length){
				s = br.readLine().split(" ");
				index = 0;
			}
			index++;
			return Double.parseDouble(s[index - 1]);
		}
	}
}