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 A implements Runnable {
	static long MOD = (long) ((1e9)+7);
	public static void main(String[] args) {
		new Thread(null, new A(), "Solver", 1L << 26).start();
	}

	private FastScanner scan;
	private PrintWriter out;

	public A() {
		scan = new FastScanner(System.in);
		out = new PrintWriter(System.out);
	}

	public void run() {
		try {
			solve();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.out.println(1 / 0);
		}
	}
	
	void solve() throws IOException {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		x = scan.nextInt();
		y = scan.nextInt();
		memo = new long[n+1];
		Arrays.fill(memo,-1);
		memo[0] = 0;
		for(int v=1;v<=n;v++) {
			if(v % 2 == 0) {
				memo[v] = Math.min(memo[v/2]+y, memo[v-1]+x);
			} else {
				memo[v] = memo[v-1]+x;
				if(v != 1)
					memo[v] = Math.min(memo[v],memo[(v+1)/2]+x+y);
			}
		}
		System.out.println(memo[n]);
	}
	static long[] memo;
	static long x,y;
	static class HLD {
		Tree tree;
		int curChainNum;
		int[] chainHead, chainPos, chainNum, chainSize;
		SegmentTree[] sts;

		public HLD(Tree tree) {
			this.tree = tree;
			int n = tree.par.length;
			curChainNum = 0;
			chainHead = new int[n];
			chainPos = new int[n];
			chainNum = new int[n];
			chainSize = new int[n];
			sts = new SegmentTree[n];
			Arrays.fill(chainHead, -1);
			buildHLD(tree.root);
			curChainNum++;
			for(int i=0;i<curChainNum;i++) {
				sts[i] = new SegmentTree(0,chainSize[i]-1);
			}
			for(int i=0;i<n;i++) {
				sts[chainNum[i]].update(chainPos[i], 0);
			}
		}
		private void buildHLD(int node) {
			if (chainHead[curChainNum] == -1) {
				chainHead[curChainNum] = node;
			}
			chainPos[node] = chainSize[curChainNum]++;
			chainNum[node] = curChainNum;

			int sn = -1, ss = -1;
			for (Edge eg : tree.edgeList[node]) {
				int e = eg.v;
				if (node != tree.par[e] || tree.subsizes[e] < ss)
					continue;
				ss = tree.subsizes[e];
				sn = e;
			}
			if (sn != -1)
				buildHLD(sn);
			for (Edge eg : tree.edgeList[node]) {
				int e = eg.v;
				if (node != tree.par[e] || e == sn)
					continue;
				curChainNum++;
				buildHLD(e);
			}
		}
		public long query(int a, int b) {
			int lca = tree.lca(a, b);
			if(a == lca) {
				return query_up(b,lca);
			}
			if(b == lca) {
				return query_up(a,lca);
			}
			return sts[0].merge(query_up(a,lca), query_up(b, lca));
		}
		public void update(int i, long value) {
			sts[chainNum[i]].update(chainPos[i], value);
		}
		public long query_up(int low, int high) {
			long ans = sts[0].defaultValue();
			while(true) {
				int lo = 0;
				int hi = chainPos[low];
				if(chainNum[low] == chainNum[high])
					lo = chainPos[high];
				if(lo > hi)
					break;
				ans = sts[chainNum[low]].merge(ans,sts[chainNum[low]].query(lo, hi));
				if(chainNum[low] == chainNum[high])
					break;
				low = chainHead[chainNum[low]];
				low = tree.par[low];
			}
			return ans;
		}


		
	}
	static class SegmentTree {
		SegmentTree left,right;
		long value;
		int min,max;
		public SegmentTree(int min, int max) {
			this.min = min;
			this.max = max;
			this.value = defaultValue();
			if(min < max) {
				this.left = new SegmentTree(min, (min+max)/2);
				this.right = new SegmentTree((min+max)/2+1, max);
			}
		}
		public long query(int qmin, int qmax) {
			if(qmin > max || qmax < min) return defaultValue();
			if(min >= qmin && max <= qmax) return value;
			return merge(left.query(qmin, qmax), right.query(qmin, qmax));
		}
		public void update(int idx, long value) {
			if(min > idx || max < idx) return;
			if(min == idx && max == idx) {
				this.value += value;
				return;
			}
			left.update(idx, value);
			right.update(idx, value);
			this.value = merge(left.value, right.value);	
		}
		public long defaultValue() {
			return 0;
		}
		public long merge(long leftValue, long rightValue) {
			return (((leftValue + rightValue) % MOD) + MOD) % MOD;
		}
	}

	static class Tree {
		int[] par;
		int[] depths;
		int[] subsizes;
		int[][] lifting;
		int root;
		ArrayList<Edge>[] edgeList;

		public Tree(ArrayList<Edge>[] edgeList, int root) {
			this.edgeList = edgeList;
			this.par = new int[edgeList.length];
			this.depths = new int[edgeList.length];
			this.subsizes = new int[edgeList.length];
			rootAt(root);
		}

		public void rootAt(int root) {
			this.root = root;
			Arrays.fill(par, -1);
			depths[root] = 0;
			par[root] = root;
			ArrayDeque<Integer> bfs = new ArrayDeque<>();
			ArrayDeque<Integer> stack = new ArrayDeque<>();
			bfs.offer(root);
			while (!bfs.isEmpty()) {
				int node = bfs.poll();
				stack.push(node);
				for (Edge eg : edgeList[node]) {
					int e = eg.v;
					if (par[e] != -1)
						continue;
					par[e] = node;
					depths[e] = depths[node] + 1;
					bfs.offer(e);
				}
			}

			while (!stack.isEmpty()) {
				int node = stack.pop();
				subsizes[node] = 1;
				for (Edge eg : edgeList[node]) {
					int e = eg.v;
					if (node != par[e])
						continue;
					subsizes[node] += subsizes[e];
				}
			}
			int n = par.length;
			int lg = Integer.numberOfTrailingZeros(Integer.highestOneBit(n)) + 2;
			lifting = new int[n][lg];
			for (int i = 0; i < n; i++)
				lifting[i][0] = par[i];
			for (int c = 1; c < lg; c++) {
				for (int i = 0; i < n; i++) {
					lifting[i][c] = lifting[lifting[i][c - 1]][c - 1];
				}
			}
		}

		public int lca(int a, int b) {
			if(depths[a] < depths[b])
				return lca(b,a);
			int diff = depths[a] - depths[b];
			while(diff > 0) {
				int bit = Integer.lowestOneBit(diff);
				a = lifting[a][Integer.numberOfTrailingZeros(bit)];
				diff -= bit;
			}
			if(a == b)
				return a;
			int lg = lifting[0].length-1;
			while(lg >= 0) {
				if(lifting[a][lg] != lifting[b][lg]) {
					a = lifting[a][lg];
					b = lifting[b][lg];
				}
				lg--;
			}
			return lifting[a][0];
		}
	}
	static class Edge {
		int u, v;
		long w;
		public Edge(int u, int v, long w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}

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

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

		public String next() throws IOException {
			while (!st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}
	}
}