B. Наша Таня громко плачет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сейчас она на самом деле не плачет. Но заплачет, если вы не решите эту задачу.

Даны числа n, k, A, B. Есть число x, которое изначально равно n. Вы можете выполнять 2 типа операций:

  1. Уменьшить x на 1, заплатив A монет.
  2. Поделить x на k, заплатив B монет. Эту операцию можно выполнять, только если x делится на k.
Какое минимальное количество монет необходимо заплатить для того, чтобы получить x = 1?
Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 2·109).

Во второй строке содержится целое число k (1 ≤ k ≤ 2·109).

В третьей строке содержится целое число A (1 ≤ A ≤ 2·109).

В четвёртой строке содержится целое число B (1 ≤ B ≤ 2·109).

Выходные данные

Выведите единственное число — минимальное количество монет, которое необходимо заплатить для того, чтобы получить x = 1.

Примеры
Входные данные
9
2
3
1
Выходные данные
6
Входные данные
5
5
2
20
Выходные данные
8
Входные данные
19
3
4
2
Выходные данные
12
Примечание

В первом тестовом примере оптимальная стратегия такова:

  • Уменьшить 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 монеты.