Codeforces 940b【贪心】

• 2018-03-06
• 904
• 0
• 0

B. Our Tanya is Crying Out Loud

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·109).

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

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

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

Output

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

Examples

input
 9
 2
 3
 1
output
 6

input
 5
 5
 2
 20
output
 8

input
 19
 3
 4
 2
output
 12

Note

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

• Subtract 1 from x (9 → 8) paying 3 coins.
• Divide x by 2 (8 → 4) paying 1 coin.
• Divide x by 2 (4 → 2) paying 1 coin.
• Divide x by 2 (2 → 1) paying 1 coin.

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.

Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long n, k, a, b, sum = 0, tmp;
    scanf("%lld%lld%lld%lld", &n, &k, &a, &b);
    if (k == 1)
    {
        printf("%lld\n", a * (n - 1));
        return 0;
    }
    while(n > 1)
    {
        tmp = n / k;
        if (n % k != 0)
        {
            if (n > k)
            {
                sum += a * (n % k); n -= n % k;
            }else
            {
                sum += a * (n - 1); n = 1;
            }
        }else
        {
            sum += min(a * (n - tmp), b); n = tmp;
        }
//        printf("**  %lld  %lld  %lld\n", n, tmp, sum);
    }
    printf("%lld\n", sum);

    return 0;
}

Origin

Codeforces 940b