现在她实际上不是。但如果你不解决这个问题,她就会这么做。
给定整数 n、k、A 和 B。有一个数字 x,最初等于 n。您可以执行两种类型的操作:
1. x 减 1。此操作需要花费您A币。
2. 将 x 除以 k。仅当 x 能被 k 整除时才能执行。这个操作需要花费你B币。
输入
第一行包含一个整数 n (1 ≤ n ≤ 2·109)。
第二行包含一个整数 k (1 ≤ k ≤ 2·109)。
第三行包含一个整数 A (1 ≤ A ≤ 2·109)。
第四行包含一个整数 B (1 ≤ B ≤ 2·109)。
输出
输出一个整数——使 x 等于 1 所需支付的最少硬币数量。
示例
输入 #1
9 2 3 1
输出 #1
6
输入 #2
5 5 2 20
输出 #2
8
输入 #3
19 3 4 2
输出 #3
12
注意
在第一个测试用例中,最优策略如下:
- 从 x (9 → 8) 中减去 1,支付 3 个硬币。
- 将 x 除以 2 (8 → 4),支付 1 个硬币。
- 将 x 除以 2 (4 → 2),支付 1 个硬币。
- 将 x 除以 2 (2 → 1),支付 1 个硬币。
总成本为 6 个硬币。
在第二个测试用例中,最佳策略是从总共支付 8 个硬币的 x 4 次中减去 1。