该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

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 \le n,k,a,b \leq 2*10^9$.

输出格式

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

输入输出样例

输入 #1

9 2 3 2

输出 #1

9

输入 #2

5 5 2 20

输出 #2

8

输入 #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$ 秒。