Сейчас она на самом деле не плачет. Но заплачет, если вы не решите эту задачу.
Даны числа n, k, A, B. Есть число x, которое изначально равно n. Вы можете выполнять 2 типа операций:
- Уменьшить x на 1, заплатив A монет.
- Поделить x на k, заплатив B монет. Эту операцию можно выполнять, только если x делится на k.
Какое минимальное количество монет необходимо заплатить для того, чтобы получить
x =
1?
Выходные данные
Выведите единственное число — минимальное количество монет, которое необходимо заплатить для того, чтобы получить x = 1.
Примечание
В первом тестовом примере оптимальная стратегия такова:
- Уменьшить x на 1 (9 → 8) за 3 монеты.
- Уменьшить x в 2 раза (8 → 4) за 1 монету.
- Уменьшить x в 2 раза (4 → 2) за 1 монету.
- Уменьшить x в 2 раза (2 → 1) за 1 монету.
Суммарная стоимость — 6 монет.
Во втором тестовом примере оптимальная стратегия — 4 раза уменьшить x на 1, потратив 8 монеты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
2
3
1
|
6
|
|
2
|
5
5
2
20
|
8
|
|
3
|
19
3
4
2
|
12
|