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^9).

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

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

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


-----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.

Difficulty: interview

Starter code:

Solutions:
import sys

def read_int():
    return int(input())

def read_ints():
    return [int(x) for x in input().split()]

n = read_int()
k = read_int()
a = read_int()
b = read_int()

cost = 0

if k == 1:
    cost = (n - 1) * a
else:
    while n != 1:
        if n % k == 0:
            if b < (n - n // k) * a:
                cost += b
            else:
                cost += (n - n // k) * a
            n = n // k
        else:
            cost += (n % k) * a
            n -= n % k
            if n == 0:
                n += 1
                cost -= a

print(cost)


from sys import stdin, stdout
from random import randrange

n = int(stdin.readline())
k = int(stdin.readline())
a = int(stdin.readline())
b = int(stdin.readline())

ans = 0

if k == 1:
    stdout.write(str((n - 1) * a))
else:
    while n != 1:
        if n % k:
            ans += (n % k) * a
            n = (n // k) * k
            continue
        
        
        if (n - (n // k)) * a <= b:
            ans += (n - 1) * a
            n = 1
        else:
            ans += b
            n //= k

    stdout.write(str(ans))

x = int(input())
k = int(input())
a = int(input())
b = int(input())

c = 0

while x > 1:
	if x % k > 0:
		if x > k:			
			c += a * (x % k)
			x -= x % k
		else:	
			c += a * (x % k - 1)
			x = 1

	else:
		if (x-x//k)*a >= b:
			c += b
			x = x//k
		else:
			c += (x-1)*a
			x = 1

print(c)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
coins = 0
while (n!=1):
	if(n%k == 0 and ((n-n/k)*A) > B):
		coins += B
		n/=k
	elif (n%k == 0):
		coins += A*(n-1)
		n = 1
	else:
		coins += A*(n%k)
		n = n - (n%k)
print(int(coins))


number = int(input())
divisor = int(input())
decrement_cost = int(input())
division_cost = int(input())

final_cost = 0
while number != 1:
	remainder = number % divisor
	if remainder != 0:
		final_cost += decrement_cost * remainder
		number -= remainder

	jump = number - number // divisor

	if division_cost < jump * decrement_cost:
		final_cost += division_cost
		number //= divisor
	else:
		final_cost += decrement_cost * (number - 1)
		number = 1

print(final_cost)

n = int(input())
k = int(input())
a = int(input())
b = int(input())
c = 0
while(n>1):
    if(n<k):
        c += a*(n - 1)
        n = 1
    else:
        if(n%k!=0):
            t = n%k
            n -= t
            c += t*a
        else:
            if(b<(n-n//k)*a):
                n = n//k
                c += b
            else:
                c += a*(n - 1)
                n = 1
print(c)


def solve(n, k, A, B):
    if k == 1:
        return A*(n-1)
    res = 0
    while n >= k:
        res += A * (n % k)
        n -= n % k
        diff = n-n//k
        if A*diff > B:
            res += B
            n //= k
        else:
            res += A*(n-1)
            n = 1 # finish loop
    res += A*(n-1)
    return res

n, k, A, B = [int(input()) for i in range(4)]
print(solve(n, k, A, B))

n = int(input());
k = int(input());
a = int(input());
b = int(input());
#inf = 100000000000000000000000000000;
ost = 0;
res = 0;
while a * (n // k) + b + (n % k) * a < n * a:
    ost = ost + (n % k) * a;
    res = res + b;
    n = n // k;
#print(n);
#print(res);
#print(ost);
res = res + (n - 1) * a + ost;
print(res);

n=int(input())
k=int(input())
a=int(input())
b=int(input())
ans=0
if k==1:
    print((n-1)*a)
    return
else:
    while n>1:
        ans+=(n%k)*a
        n-=n%k
        if b>(n-n//k)*a:
            print((n-1)*a+ans)
            return
        else:
            n//=k
            ans+=b
print(ans)
    
    
    


n=int(input())
k=int(input())
a=int(input())
b=int(input())
x=n
c=0
if k==1:
    c=a*(n-1)
else:
    while x>=k:
        y=x%k
        c+=y*a
        x-=y
        c+=min(b,a*(x-x//k))
        x=(x//k)
    c+=a*(x-1)
print(c)

n = int(input())
k = int(input())
A = int(input())
B = int(input())

ans = 0
if k == 1:
	print(A*(n-1))
	return

while n > 1:
	subt = (n % k)
	ans += A * subt
	n -= (n%k)
	ans += min(A * (n - (n // k)),B)
	n //= k

if n == 0:
	ans -= A

print(ans)

n = int(input())
k = int(input())
a = int(input())
b = int(input())

r = 0

if k == 1:
    print((n - 1) * a)
    return

while n != 1:
    if n % k != 0:
        r += n % k * a
        n -= n % k
    elif n < k:
        r += (n - 1) * a
        n = 1
    else:
        if n // k * (k - 1) * a < b:
            r += n // k * (k - 1) * a
        else:
            r += b
        n //= k
print(r)


n=int(input())
k=int(input())
a=int(input())
b=int(input())
ans=0
if ((k==1)|(k>n))&(n!=1):
    ans=n*a-a
    n=1
while (n!=1):
    if (n%k==0):
        t=n//k
        y=n-t
        if (y*a<=b):
            ans+=n*a-a
            n=1
        else:
            ans+=b
            n=t
    else:
        ans+=(n%k)*a
        n-=n%k
print(ans)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
x = n
cost = 0

if k == 1:
    print(int((x - 1) * a))
    return

while x > 1:
    if x < k:
        cost += (x - 1) * a
        break
    rem = x % k
    x -= rem
    cost += a * rem
    if rem == 0:
        temp = (x // k) * (k - 1)
        x //= k
        cost += min(temp * a, b)

print(cost)


from sys import stdin as cin

def main():
    n = int(cin.readline())
    k = int(cin.readline())
    a = int(cin.readline())
    b = int(cin.readline())
    o = 0
    if k == 1:
        print((n - 1) * a)
        return
    while n > 1:
        if n % k:
            t = n - n // k * k
            if t == n:
                t -= 1
            o += a * t
            n -= t
        else:
            t = n // k
            o += min(a * (n - t), b)
            n = t
        #print(n, o)
    print(o)

main()


n = int(input())
k = int(input())
A = int(input())
B = int(input())

res = 0
while n>k:
    if n % k >0:
        res += (n%k) * A
        n -= (n%k)

    dif  = n - (n//k)
    if dif*A > B:
        res += B
        n = n//k
    else:
        res += (n-1)*A
        n = 1

if n == k:
    dif  = n - (n//k)
    if dif*A > B:
        res += B
        n = n//k
    else:
        res += (n-1)*A
        n = 1

if n >1 :
    res += (n-1)*A
    n = 1
print(res)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
ans = 0
if k > 1:
    while n > 1:
        new_n = max(1, n // k * k)
        ans += (n - new_n) * a
        n = new_n
        while n % k == 0:
            new_n = n // k
            ans += min((n - new_n) * a, b)
            n = new_n
else:
    ans = (n - 1) * a
print(ans)

n, k, A, B = (int(input()) for i in range(4))

if k == 1:
    print((n - 1) * A)

else:
    x = n
    ans = 0

    while x != 1:
        if 1 < x < k:
            ans += (x - 1) * A
            x = 1
        else:
            if x % k != 0:
                ans += (x - (x // k) * k) * A
                x = (x // k) * k

            else:
                d = x - (x // k)
                ans += min(d * A, B)
                x //= k

    print(ans)


inf = 0x3f3f3f3f3f3f3f3f
M = mod = 1000000007
mod2inv = 500000004
pt = lambda *a, **k: print(*a, **k, flush=True)
rd = lambda: map(int, input().split())
n = int(input())
k = int(input())
a = int(input())
b = int(input())
r = 0
if k == 1:
    print((n - 1) * a)
    return
while n:
    if n % k:
        r += n % k * a
        n -= n % k
    r += min(b, (n - n // k) * a)
    n //= k
pt(r - a)



n=int(input())
k=int(input())
a=int(input())
b=int(input())
x=n
c=0

if k==1:
	print(a*(n-1))
elif k > x:
	print(a*(x-1))
else:
	while x>=k:
		if x%k==0:
			temp=x/k
			if b < (x-(temp))*a:
				c+=b
				x=temp
			else:
				c+=a*(x-(temp))
				x=temp
		else:
			t=x%k
			c+=(a*t)
			x=x-t
	if x==1:
		print(int(c))
	else:
		print(int(c)+int((x-1)*a))


n = int(input(""))
k = int(input(""))
a = int(input(""))
b = int(input(""))

ans = 0
while not n == 1:
	m = n % k
	n = n - m
	ans = ans + m*a

	if (n-(n/k))*a > b:
		n = n / k
		ans = ans + b
	else:
		ans = ans + (n-1)*a
		n = 1
print(int(ans)) 
"""
	int64 ans = 0;
	while(n != 1){
		int64 m = n % k;
		n -= m;
		//cout << "m " << m << endl;
		ans += m*a;

		if((n-(n/k))*a > b){
			n /= k;
			ans += b;
		}else{
			ans += (n-1)*a;
			cout << ans;
			return 0;
		}

	}	
	
	cout << ans;
"""

n = int(input())
k= int(input())
a = int(input())
b = int(input())
res = 0
if k == 1:
    print((n - 1) * a)
else:
    while n != 1:
        res += (n % k) * a
        if b > (n // k)*(k - 1) * a:
            res += (n // k)*(k - 1) * a
        else:
            res += b
        n //= k
        if n < k:
            res += (n - 1) * a
            break
    print(res)

n = int(input())
k = int(input())
c1 = int(input())
c2 = int(input())
if k == 1:
	k += n
ans = 0
while n > 1:
	if n > k:
		temp = n % k
		ans += temp * c1
		n -= temp
	if n % k == 0:
		ans += min(c2, (n - n // k) * c1)
		n //= k
	else:
		ans += (n - 1) * c1
		n = 1
print(ans)

n = int(input())
k = int(input())
a = int(input())
b = int(input())
ans = 0
while n != 1:
    if n % k == 0:
        d = n // k
        if b >= (n-d)*a:
            ans += (n-1)*a
            n=1
        else:
            ans += b
            n = d
    else:
        r = n % k
        ans += r*a
        n = n - r
print(ans)