← 返回题目列表

Codeforces · 940/B

B. 我们的坦尼娅大声哭喊

中文机器翻译题面 查看原题

现在她实际上不是。但如果你不解决这个问题,她就会这么做。

给定整数 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。