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.awt.List;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.*;


 
 
public class ck {

	private static InputStream stream;
	private static PrintWriter pw;
	
	
	
//	static int a;
//	static int b;
//	static int f = 0;
//	static int n;
//	static int m;
//	static char[][] arr;
	

	
//	static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};

//	static int visited[][];
	
	
//	static ArrayList<Integer> ans;

//	static int arr[][];
//	static int arr[];
//	static char[][] arr;
//	static int[][] visited;
//  static int c;
//	static int d[];
//	static int arr[][];
//	static ArrayList<Integer> arr[];
	static ArrayList<Integer> comp[];
	
	//static int c;
	static int parent[];
	static int nodes;
	static long ans = 0;
	static long a;
	static long d;
	static int n;
	
	public static void main(String[] args) throws NumberFormatException, IOException{
		//InputReader(System.in);
		//pw = new PrintWriter(System.out);
		
		Scanner in = new Scanner(System.in);
		
//		int t = in.nextInt();
//		in.nextLine();
//		
//		for(int j = 0;j<t;j++){

		n = in.nextInt();
		a = in.nextLong();
		d = in.nextLong();
		  	
		long ans = dfs(n);
    	System.out.println(ans);
}
	
	
	public static long dfs(int i){
		
		if(i == 1){
			return a;
		}
		
		if(i == 2){
			return a + (long)Math.min(a, d);
		}
		
		if(i%2 == 0){
			
			if((i/2)*a < d){
				return dfs(i/2) + (long)(i/2)*a;
			}else{
				return dfs(i/2) + d;
			}
		}else{
			return (long)Math.min(dfs(i-1),dfs(i+1)) + a;
		}
		
		
	}
public static void ddfs(int n,int m,int i,int j,char arr[][],int visited[][],int dir[][],int store[][],int ans){
		
		if(visited[i][j] == 1){
			return;
		}
		
		
		//System.out.println(i + " " + j + " " + arr[i][j]);
		if(arr[i][j] == '*'){
			ans++;
			return;
		}
		
		visited[i][j] = 1;
		store[i][j] = ans;
		int x = i;
		int y = j;
		
		for(int p = 0;p<4;p++){
			
			i = x + dir[p][0];
			j = y + dir[p][1];
			
			if(i < 0 || i >= n|| j < 0 || j >=m){
				
			}else{
				dfs(n,m,i,j,arr,visited,dir);
			}
			
		}
		
		
	}
	
	
	public static void dfs(int n,int m,int i,int j,char arr[][],int visited[][],int dir[][]){
		
		if(visited[i][j] == 1){
			return;
		}
		
		
		//System.out.println(i + " " + j + " " + arr[i][j]);
		if(arr[i][j] == '*'){
			ans++;
			return;
		}
		
		visited[i][j] = 1;
		int x = i;
		int y = j;
		
		for(int p = 0;p<4;p++){
			
			i = x + dir[p][0];
			j = y + dir[p][1];
			
			if(i < 0 || i >= n|| j < 0 || j >=m){
				
			}else{
				dfs(n,m,i,j,arr,visited,dir);
			}
			
		}
		
		
	}
	
	

//	
//	public static void bfs(int i){
//		
//		Queue<Integer> q=new LinkedList<Integer>();
//    	q.add(i);
//    	
//    	visited[i] = 1;
//    	c++;
//    	nodes++;
//    	while(!q.isEmpty()){
//    		int top=q.poll();
//    		
//    		Iterator<Integer> it= arr[top].listIterator();
//    		while(it.hasNext()){
//    			int next =it.next();
//    			
//    			if(visited[next] == 0){
//    				nodes++;
//    				visited[next] = 1;
//    				q.add(next);
//    			}
//    		
//    		}
//    	}
//		
//	}
	
	
	public static void union(int a,int b){
		a = find(a);
		b = find(b);
		
		parent[a] = b;
		return;
	}
	
	public static int find(int i){
		if(i == parent[i]){
			return i;
		}
		
		parent[i] = find(parent[i]);
		return parent[i];
	}
	
//	public static void dfs(int i){
//		
//		
//		if(visited[i] == 1){
//			return;
//		}
//		
//		visited[i] = 1;
//		con[c].add(i);
//		//System.out.print(i + " ");
//		for(int j = 0;j<arr[i].size();j++){
//			dfs(arr[i].get(j));
//		}
//		
//	}
//	
//	
//	public static void dfss(int i){
//		if(visited[i] == 1){
//			return;
//		}
//		
//		visited[i] = 1;
//		
//		for(int j = 0;j<arr[i].size();j++){
//			dfss(arr[i].get(j));
//		}
//	//	System.out.println(i);
//		stack.push(i);
//	}
//	
//	public static void reverse(){
//		ArrayList[] temp = new ArrayList[n];
//		
//		for(int i = 0;i<n;i++){
//			temp[i] = new ArrayList();
//		}
//		
//		for(int i = 0;i<n;i++){
//			for(int j = 0;j<arr[i].size();j++){
//				temp[arr[i].get(j)].add(i);
//			}
//		}
//		
//		arr = temp;
//		
//	}
//	
//	
	
	
	
	
	
	
	public static boolean isPrime(int n) {
		// Corner cases
		if (n <= 1)
			return false;
		if (n <= 3)
			return true;
 
		// This is checked so that we can skip 
		// middle five numbers in below loop
		if (n % 2 == 0 || n % 3 == 0)
			return false;
 
		for (int i = 5; i * i <= n; i = i + 6)
			if (n % i == 0 || n % (i + 2) == 0)
				return false;
 
		return true;
	}
	
	
	
	public static void Range(int[] numbers, int target) {
	    if (numbers == null)
	        return;

	    int low = 0, high = numbers.length - 1;
	    // get the start index of target number
	    int startIndex = -1;
	    while (low <= high) {
	        int mid = (high - low) / 2 + low;
	        if (numbers[mid] > target) {
	            high = mid - 1;
	        } else if (numbers[mid] == target) {
	            startIndex = mid;
	            high = mid - 1;
	        } else
	            low = mid + 1;
	    }

	    // get the end index of target number
	    int endIndex = -1;
	    low = 0;
	    high = numbers.length - 1;
	    while (low <= high) {
	        int mid = (high - low) / 2 + low;
	        if (numbers[mid] > target) {
	            high = mid - 1;
	        } else if (numbers[mid] == target) {
	            endIndex = mid;
	            low = mid + 1;
	        } else
	            low = mid + 1;
	    }

	    if (startIndex != -1 && endIndex != -1){
	        for(int i=0; i+startIndex<=endIndex;i++){
	            if(i>0)
	                System.out.print(',');
	            System.out.print(i+startIndex);
	        }
	    }
	}
	
	 // union code starts	
	
	 private static void initialize( int Arr[ ],int size[], int N)
	    {
	        for(int i = 0;i<N;i++)
	        {
	        	Arr[ i ] = i ;
	        	size[ i ] = 1;
	        }
	    }
	 
	 private static int root(int Arr[ ],int i)
	    {
	        while(Arr[ i ] != i)           //chase parent of current element until it reaches root
	        {
	            Arr[ i ] = Arr[ Arr[ i ] ] ; 
	            i = Arr[ i ];
	        }
	        return i;
	    }
	 
	 private static void union(int Arr[ ],int size[ ],int A,int B)
	    {
	        int root_A = root(Arr,A);
	        int root_B = root(Arr,B);
	     
	        if(root_A != root_B){
	        	 if(size[root_A] < size[root_B ])
	 	        {
	        		 Arr[ root_A ] = Arr[root_B];
	        		 size[root_B] += size[root_A];	 	
	 	        }
	 	        else
	 	        {   	
	 	        	Arr[ root_B ] = Arr[root_A];
	 	        	size[root_A] += size[root_B];	 	   
	 	        }	
	        }
	    }
	 
	 private static boolean find(int Arr[],int A,int B)
	    {
	        if( root(Arr,A)==root(Arr,B) )       //if A and B have the same root, it means that they are connected.
	        return true;
	        else
	        return false;
	    }
	 
	 
	 // union code ends
	
	
	 
//	 // Segment tree code begins
//	 
//	 
//	 static void build(int node,int start,int end)
//	 {
//	 if(start==end)
//	 tree[node]=a[start];
//	 else
//	 {
//	 int mid=(start+end)/2;
//	 build(2*node,start,mid);
//	 build(2*node+1,mid+1,end);
//	 if(tree[2*node]<tree[2*node+1])
//	 tree[node]=tree[2*node];
//	 else
//	 tree[node]=tree[2*node+1];
//	 }
//	 }
//	 
//	 
//	 static void update(int node,int start,int end,int idx,int val)
//	 {
//	 if(start==end)
//	 {
//	 a[idx]=val;
//	 tree[node]=val;
//	 }
//	 else
//	 {
//	 int mid=(start+end)/2;
//	 if(idx>=start&&idx<=mid)
//	 update(2*node,start,mid,idx,val);
//	 else
//	 update(2*node+1,mid+1,end,idx,val);
//	 if(tree[2*node]<tree[2*node+1])
//	 tree[node]=tree[2*node];
//	 else
//	 tree[node]=tree[2*node+1];
//	 }
//	 }
//	 
//	 static int query(int node,int start,int end,int l,int r)
//	 {
//	 if(l>end||start>r)
//	 return 100005;
//	 if(l<=start&&r>=end)
//	 return tree[node];
//	 int p1,p2;
//	 int mid=(start+end)/2;
//	 p1=query(2*node,start,mid,l,r);
//	 p2=query(2*node+1,mid+1,end,l,r);
//	 if(p1<p2)
//	 return p1;
//	 else
//	 return p2;
//	 }
//	 
//	 
//	 
//}

}

class Node{
	int a;
	int b;
}


class MyComp2 implements Comparator<Node>{
    
	@Override
	public int compare(Node o1, Node o2) {
		if(o1.a>o2.a){
			return 1;
		}else if(o1.a<o2.a){
			return -1;
		}else{
			if(o1.b>o2.b){
				return 1;
				
			}else{
				return -1;
			}
			
			
		}
		
		
	}
}


class Card implements Comparable<Card>
{
	int w,h,index;
	public Card(int w,int h,int index)
	{
		this.w=w;
		this.h=h;
		this.index=index;
	}
	public int compareTo(Card that)
	{
		return this.w-that.w;
	}
}