A. 进度条

小聪最近在玩的游戏有一个每日任务，需要把进度条清空。

小聪已经厌倦了自己日复一日清空进度条，于是求小潘来帮忙。

具体来说，这个进度条的数值一开始是 $n$，当数值变成 $1$ 的时候，代表进度条被清空。

小潘有特殊的进度条清理手段，她有两种操作：

进度条数值减去 $1$，花费的体力为 $a$； 进度条数值除以 $k$，花费的体力为 $b$，这种操作只有在进度条数值是 $k$ 的倍数的时候才能进行。 请计算小潘最少需要多少体力能帮小聪清空进度条。

输入格式

一行，四个整数表示 $n, k, a, b$。

输出格式

一行，表示最小花费的体力。

样例输入1

9 2 3 1

样例输出1

6

样例输入2

5 5 2 20

样例输出1

8

数据范围

对于 $30\%$ 的数据，$1 \leq n, k, a, b \leq 10^3$。

对于 $100\%$ 的数据，$1 \leq n, k ,a, b \leq 2 \times 10 ^ 9$。