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

Тяжела жизнь системного администратора в крупной компании! То у одного из сотрудников не работает принтер, то у другого отключился интернет. Передохнуть нельзя ни секунды.

Сегодня рабочий день системного администратора Миши начался со звонка секретаря Тани, которая в очередной раз не справилась с редактированием документа. Миша моментально пришёл к Тане и узнал, что в результате ошибки в папке на ее компьютере оказалось n копий документа, над которым она сейчас работает. Других документов в папке нет. Таня просит Мишу удалить лишние копии, чтобы у неё осталась ровно одна копия нужного файла.

Таня работает в операционной системе Bububuntu, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Bububuntu эта команда работает, только если количество файлов в папке делится на k без остатка. На выполнение этой команды Миша тратит B секунд.

Для решения Таниной проблемы Миша решил по очереди использовать эти команды таким образом, чтобы в конце в папке остался ровно один документ.

У Миши сегодня много других дел, поэтому он хочет справиться с проблемой как можно быстрее. Помогите Мише и скажите, за какое минимальное количество секунд он сможет решить Танину проблему, если будет действовать оптимально.

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

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

Во второй строке содержится целое число k (1 ≤ k ≤ 2·109) — количество раз, в которое уменьшает количество файлов вторая команда.

В третьей строке содержится целое число A (1 ≤ A ≤ 2·109) — количество секунд, которое Миша тратит на выполнение первой команды.

В четвёртой строке содержится целое число B (1 ≤ B ≤ 2·109) — количество секунд, которое Миша тратит на выполнение второй команды.

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

Выведите единственное число — минимальное количество секунд, которое придётся потратить Мише на решение проблемы.

Примеры

Входные данные
9
2
3
1
Выходные данные
6
Входные данные
5
5
2
20
Выходные данные
8
Входные данные
19
3
4
2
Выходные данные
12

Примечание

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

На выполнение этих четырёх операций Миша потратит 6 секунд. Можно показать, что Миша не сможет удалить лишние файлы меньше, чем за 6 секунд.

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как её выполнение занимает 20 секунд, Мише это не выгодно.

Система оценки

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, работающие при 1 ≤ n, k, A, B ≤ 20 будут набирать не менее 20 баллов.

Решения, работающие при 1 ≤ n, k, A, B ≤ 100 будут набирать не менее 40 баллов.

Решения, работающие при 1 ≤ n, k, A, B ≤ 106 будут набирать не менее 60 баллов.