Гра#8587

Гра

1 секунда

128 мегабайтів

Складна

Джон і Джордж грають у гру з наступними правилами: Джон вибирає ціле число $x$ з множини $A_{n} = {1, 2, 3, \dots, n}$ A_n = \{1, 2, 3, \ldots, n\}. Завдання Джорджа — вгадати це число $x$ . Гравці ходять по черзі: $1$ , $2$ , ... . На $k$ -му ході Джордж вибирає підмножину $B_{k}$ B_k з $A_{n}$ A_n, і Джон відповідає YES, якщо $x$ належить $B_{k}$ B_k, або NO в іншому випадку. Якщо відповідь NO, Джордж платить Джону $a$ євро; якщо YES, Джордж платить $b$ євро. Потрібно визначити мінімальну суму в євро, яку Джордж повинен заплатити, щоб гарантовано знайти $x$ , незалежно від вибору Джона.

Напишіть програму, яка обчислить цю мінімальну суму.

Вхідні дані

В одному рядку задано три цілі числа $n$ ( $1 < n < 1 0^{18}$ 1 < n < 10^{18}), $a$ і $b$ ( $0 < a, b < 1000$ 0 < a, b < 1000).

Вихідні дані

Виведіть одне ціле число, яке дорівнює мінімальній сумі в євро, необхідній для визначення $x$ .

Приклади

Приклад 1

Примітка

Джордж може знайти $x$ за $4$ євро наступним чином:

Джордж вибирає множину $B_{1} = {1, 2}$ B_1 = \{1, 2\}.

Якщо Джон відповідає YES, Джордж платить $2$ євро і потім вибирає множину $B_{2} = {1}$ B_2 = \{1\}. Якщо наступна відповідь YES, Джордж платить ще $2$ євро, і гра завершується (задумане число — $1$ ), інакше він платить ще $1$ євро, і гра завершується (задумане число — $2$ ).
Якщо Джон відповідає NO, Джордж платить $1$ євро і потім вибирає множину $B_{2} = {3}$ B_2 = \{3\}. Якщо наступна відповідь YES, Джордж платить ще $2$ євро, і гра завершується (задумане число — $3$ ), інакше він платить ще $1$ євро і вибирає множину $B_{3} = {4}$ B_3 = \{4\}. Якщо остання відповідь YES, Джордж платить ще $2$ євро, і гра завершується (задумане число — $4$ ), інакше Джордж платить ще $1$ євро, і гра завершується (задумане число — $5$ ).