Задача №113766. Наша Таня громко плачет
Тяжела жизнь системного администратора в крупной компании! То у одного из сотрудников не работает принтер, то у другого отключился интернет. Передохнуть нельзя ни секунды.
Сегодня рабочий день системного администратора Миши начался со звонка секретаря Тани, которая в очередной раз не справилась с редактированием документа. Миша моментально пришёл к Тане и узнал, что в результате ошибки в папке на ее компьютере оказалось n копий документа, над которым она сейчас работает. Других документов в папке нет. Таня просит Мишу удалить лишние копии, чтобы у неё осталась ровно одна копия нужного файла.
Таня работает в операционной системе Bububuntu, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Bububuntu эта команда работает, только если количество файлов в папке делится на k без остатка . На выполнение этой команды Миша тратит B секунд.
Для решения Таниной проблемы Миша решил по очереди использовать эти команды таким образом, чтобы в конце в папке остался ровно один документ.
У Миши сегодня много других дел, поэтому он хочет справиться с проблемой как можно быстрее. Помогите Мише и скажите, за какое минимальное количество секунд он сможет решить Танину проблему, если будет действовать оптимально.
В первой строке содержится целое число n ( 1 ≤ n ≤ 2·10 9 ) — количество копий документа в папке у Тани.
Во второй строке содержится целое число k ( 1 ≤ k ≤ 2·10 9 ) — количество раз, в которое уменьшает количество файлов вторая команда.
В третьей строке содержится целое число A ( 1 ≤ A ≤ 2·10 9 ) — количество секунд, которое Миша тратит на выполнение первой команды.
В четвёртой строке содержится целое число B ( 1 ≤ B ≤ 2·10 9 ) — количество секунд, которое Миша тратит на выполнение второй команды.
Выведите единственное число — минимальное количество секунд, которое придётся потратить Мише на решение проблемы.
В первом тестовом примере оптимальная стратегия Миши такова:
- За 3 секудны удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2 .
- За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.
- За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.
- За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.
На выполнение этих четырёх операций Миша потратит 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 ≤ 10 6 будут набирать не менее 60 баллов.
9 2 3 1
6
5 5 2 20
8
19 3 4 2
12