CF940B Our Tanya is Crying Out Loud

现在她实际上并没有生气。但如果你不解决这个问题，她就会生气。 给定整数 $n$、$k$、$A$ 和 $B$。有一个数 $x$，初始时 $x=n$。你可以进行两种操作： 1. 使 $x$ 减 $1$。每次操作需要花费 $A$ 个硬币。 2. 将 $x$ 除以 $k$。仅当 $x$ 能被 $k$ 整除时才能进行此操作。每次操作需要花费 $B$ 个硬币。 你需要支付的最少硬币数是多少，才能使 $x$ 变为 $1$？

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^{9}$）。 第二行包含一个整数 $k$（$1 \leq k \leq 2 \cdot 10^{9}$）。 第三行包含一个整数 $A$（$1 \leq A \leq 2 \cdot 10^{9}$）。 第四行包含一个整数 $B$（$1 \leq B \leq 2 \cdot 10^{9}$）。

输出一个整数，表示将 $x$ 变为 $1$ 所需支付的最少硬币数。

在第一个测试样例中，最优策略如下： - 使 $x$ 减 $1$（$9 \to 8$），花费 $3$ 个硬币。 - 将 $x$ 除以 $2$（$8 \to 4$），花费 $1$ 个硬币。 - 将 $x$ 除以 $2$（$4 \to 2$），花费 $1$ 个硬币。 - 将 $x$ 除以 $2$（$2 \to 1$），花费 $1$ 个硬币。 总共花费 $6$ 个硬币。 在第二个测试样例中，最优策略是将 $x$ 连续减 $1$ 共 $4$ 次，总共花费 $8$ 个硬币。 由 ChatGPT 4.1 翻译