Right now she actually isn't. But she will be, if you don't solve this problem.

You are given integers n, k, A and B. There is a number x, which is initially equal to n. You are allowed to perform two types of operations:

Subtract 1 from x. This operation costs you A coins.
Divide x by k. Can be performed only if x is divisible by k. This operation costs you B coins.

What is the minimum amount of coins you have to pay to make x equal to 1?

Input

The first line contains a single integer n (1 ≤ n ≤ 2·10⁹).

The second line contains a single integer k (1 ≤ k ≤ 2·10⁹).

The third line contains a single integer A (1 ≤ A ≤ 2·10⁹).

The fourth line contains a single integer B (1 ≤ B ≤ 2·10⁹).

Output

Output a single integer — the minimum amount of coins you have to pay to make x equal to 1.

Note

In the first testcase, the optimal strategy is as follows:

The total cost is 6 coins.

In the second test case the optimal strategy is to subtract 1 from x 4 times paying 8 coins in total.

Our Tanya is Crying Out Loud