题目背景

To the greatest All-around King zsp！

题目描述

伟大的运维专家zsp正在管理他的服务器。

某一时刻，他的服务器有n个进程。由于内存的限制，他需要将其中n-1个进程关闭而只留下1个进程。

设剩余进程数为x，zsp在每次关闭进程时有两种操作(都无操作次数限制)：

1.关闭1个进程，即x=x-1，这会消耗a秒的时间；

2.将剩余进程数x变为x/k。该操作只有当x能被k整除时才可使用。这会消耗b秒的时间.

那么将n个进程减少为1个进程的最小时间是多少?

输入格式

一行，包括n,k,a,b，分别表示总进程数，除数，操作1所需时间和操作2所需时间.其中,1<=n,k,a,b<=2*$10^9$.

输出格式

输出一个整数t表示将总进程数n变为1所需的最小时间（不用输出单位秒）。

输入输出样例 #1

输入 #1

9 2 3 2

输出 #1

9

输入输出样例 #2

输入 #2

5 5 2 20

输出 #2

8

输入输出样例 #3

输入 #3

19 3 4 2

输出 #3

12

说明/提示

对第一组样例，可以进行如下操作

第一步选择操作1,剩余进程数变为9-1=8,消耗3秒。

第二步选择操作2，剩余进程变为8/2=4,消耗2秒。

第三步选择操作2，剩余进程变为4/2=2，消耗2秒。

第四步选择操作2,剩余进程变为2/2=1，消耗2秒。

则总的最小时间为9秒。