给定四个正整数n, k, A和B，现有一个整数x，它最初等于n。您可以对x执行以下两种操作任意次:

（1）x减去1。这个操作会花费你A个硬币。

（2）x除以k（只有当x能被k整除时才能执行）。这个操作会花费你B个硬币。

请问：让x等于1所需要花费的最少硬币是多少?

第一行为整数n(1≤n≤2*10⁹)。

第二行为整数k(1≤k≤2*10⁹)。

第三行为整数A(1≤A≤2*10⁹)。

第四行为整数B(1≤B≤2*10⁹)。

一行一个整数：让x等于1所需要花费的最少硬币数。

测试样例2输入：

测试样例2输出：

8

在第一个测试用例中，最优策略如下: 

x减去1(9→8)支付3个硬币。

x除以2(8→4)支付1枚硬币。

x除以2(4→2)支付1枚硬币。

x除以2(2→1)支付1个硬币。

总花费是6个硬币。