수 맞히기 게임

존과 조지가 다음 게임을 한다. 존은 집합 $A_n = \{1, 2, 3, \ldots, n\}$에서 정수 $x$ 하나를 고르고, 조지는 그 $x$가 무엇인지 알아내야 한다. 게임은 $1, 2, 3, \ldots$번째 차례로 이어진다. $k$번째 차례에 조지가 $A_n$의 부분집합 $B_k$를 고르면, 존은 $x$가 $B_k$에 들어 있으면 YES, 아니면 NO라고 답한다. 답이 NO면 조지는 존에게 $a$유로를 내고, YES면 $b$유로를 낸다.

조지는 답을 하나 들을 때마다 그 답을 보고 다음 부분집합을 정할 수 있다. $x$가 무엇이든 반드시 알아내는 전략 중에서 조지가 내는 금액의 최댓값이 가장 작은 전략을 찾고, 그때의 금액을 구하는 프로그램을 작성하라.

첫 줄에 정수 $n$, $a$, $b$가 공백으로 구분되어 주어진다.

조지가 내야 하는 최소 금액을 정수 하나로 출력한다.

• $1 < n < 10^{18}$
• $0 < a, b < 1\,000$

$n = 5$, $a = 1$, $b = 2$이면 조지는 4유로로 $x$를 알아낼 수 있다.

조지가 먼저 $B_1 = \{1, 2\}$를 고른다.

• 존이 YES라고 답하면 조지는 2유로를 내고 $B_2 = \{1\}$을 고른다. 다시 YES면 2유로를 더 내고 게임이 끝난다($x = 1$). NO면 1유로를 더 내고 게임이 끝난다($x = 2$).
• 존이 NO라고 답하면 조지는 1유로를 내고 $B_2 = \{3\}$을 고른다. YES면 2유로를 더 내고 게임이 끝난다($x = 3$). NO면 1유로를 더 내고 $B_3 = \{4\}$를 고른다. YES면 2유로를 더 내고 게임이 끝난다($x = 4$). NO면 1유로를 더 내고 게임이 끝난다($x = 5$).

가장 많이 내는 경우는 $x = 1$일 때와 $x = 4$일 때이고, 두 경우 모두 4유로다.