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: MEDIUM
Tags: Dynamic programming

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
n = int(input())
k = int(input())
A = int(input())
B = int(input())
kapa = 0
if k == 1:
	print((n - 1) * A)
else:
	while n != 1:
		if n < k:
			kapa += (n - 1) * A
			n = 1
		elif n % k == 0:
			kapa += min(B, (n - n // k) * A)
			n //= k
		else:
			kapa += A * (n - n // k * k)
			n = n // k * k
	if n == 0:
		kapa += 1
	print(kapa)


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 = int(input())
k = int(input())
a = int(input())
b = int(input())
cost = 0
if k == 1:
	print((n - 1) * a)
	exit()
while n != 1:
	if n % k == 0:
		if b > (n - n // k) * a:
			cost += (n - n // k) * a
			n = n // k
		else:
			cost += b
			n = n // k
	elif n < k:
		cost += (n - 1) * a
		n = 1
	else:
		cost += a * (n % k)
		n -= n % k
print(cost)


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())
A = int(input())
B = int(input())
if k == 1:
	n -= 1
	print(n * A)
	exit(0)
cnt = 0
while n > 1:
	if n < k:
		x = n - 1
		cnt += x * A
		break
	r = n % k
	if r != 0:
		cnt += A * r
		n -= r
	else:
		x = n - n // k
		cnt += min(B, x * A)
		n //= k
print(cnt)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
x = n
cost = 0
while x > 1:
	if k == 1:
		cost += (x - 1) * A
		break
	res = x % k
	if res == 0:
		pre_x = x // k
		pre_cost_B = B
		pre_cost_A = (x - pre_x) * A
		cost += min(pre_cost_A, pre_cost_B)
		x = pre_x
	else:
		x -= res
		if x >= k:
			cost += res * A
		else:
			cost += (res - 1) * A
print(cost)


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


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


n = int(input())
k = int(input())
A = int(input())
B = int(input())
ans = 0
if k == 1:
	print(A * (n - 1))
	exit(0)
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)


x = int(input())
k = int(input())
a = int(input())
b = int(input())
cost = 0
av_a = 0
av_b = 0
if a == 0:
	cost = 0
elif k == 1:
	cost = (x - 1) * a
else:
	while x > 1:
		if x % k != 0:
			if x > k:
				w = x % k
				x = x - w
				cost = cost + w * a
			else:
				cost = cost + (x - 1) * a
				x = 1
		elif x % k == 0:
			av_a = a
			av_b = b / (x - x / k)
			if av_a >= av_b:
				x = x / k
				cost = cost + b
			elif av_a < av_b:
				cost = cost + a * (x - x / k)
				x = x / k
print('%d' % cost)


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


x = int(input())
k = int(input())
A = int(input())
B = int(input())
ans = 0
while x != 1:
	if x < k or k == 1:
		ans += (x - 1) * A
		x -= x - 1
	elif x % k != 0:
		ans += x % k * A
		x -= x % k
	else:
		ans += min(B, (x - x // k) * A)
		x = x // k
print(ans)


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


x = []
for i in range(4):
	x.append(int(input()))
n = x[0]
k = x[1]
a = x[2]
b = x[3]
cost = 0
x = n
while int(x) != 1:
	if k == 1:
		cost = cost + (x - 1) * a
		x = 1
	elif x < k:
		cost = cost + (x - 1) * a
		x = 1
	elif x == k:
		if b > (x - 1) * a:
			cost = cost + (x - 1) * a
			x = 1
		else:
			cost = cost + b
			x = 1
	elif x > k:
		re = x % k
		if re > 0:
			cost = cost + re * a
			x = x - re
		elif b < (x - x / k) * a:
			cost = cost + b
			x = int(x / k)
		else:
			cost = cost + (x - x / k) * a
			x = int(x / k)
print(int(cost))


from sys import stdin
(n, k, a, b) = [int(stdin.readline()) for i in range(4)]
ans = 0
if k == 1:
	ans = a * (n - 1)
else:
	while n > 1:
		(div, mod) = divmod(n, k)
		if mod:
			ans += mod * a
			n -= mod
			if not n:
				ans -= a
		else:
			x1 = a * (n - div)
			ans += min(b, x1)
			n = div
print(ans)


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


(n, k, A, B) = (int(input()), int(input()), int(input()), int(input()))
if k == 1:
	print((n - 1) * A)
else:
	ans = (n - 1) * A
	for i in range(1, 64):
		pw = k ** i
		if pw > n:
			break
		(cur_ans, x) = (i * B, n - pw)
		while pw > 0:
			cur_ans += A * (x // pw)
			x %= pw
			pw //= k
		ans = min(ans, cur_ans)
	print(ans)


import sys
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
A = int(sys.stdin.readline())
B = int(sys.stdin.readline())
if k == 1:
	print((n - 1) * A)
else:
	ans = 0
	while True:
		x = n // k * k
		ans += (n - x) * A
		n = x
		if (n - n // k) * A <= B:
			break
		n //= k
		ans += B
	print(ans + (n - 1) * A)


n = int(input())
k = int(input())
a_cost = int(input())
b_cost = int(input())
x = n
if k == 1:
	result = (x - 1) * a_cost
else:
	result = 0
	result += x % k * a_cost
	x -= x % k
	while b_cost < (x - x // k) * a_cost:
		result += b_cost
		x //= k
		result += x % k * a_cost
		x -= x % k
	if x != 0:
		result += (x - 1) * a_cost
	else:
		result -= a_cost
print(result)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
c = 0
x = n
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())
if k == 1:
	print((n - 1) * a)
	exit()
price = 0
while n != 1:
	if n % k == 0:
		price += min((n - n // k) * a, b)
		n //= k
	else:
		price += min(n % k, n - 1) * a
		n = max(1, n - n % k)
print(price)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
cost = 0
if k != 1:
	while n != 1:
		if n < k:
			cost += (n - 1) * A
			n = 1
		elif n % k == 0:
			res = n // k
			costA = B
			costB = (n - res) * A
			n = res
			cost += min(costA, costB)
		else:
			res = n // k * k
			cost += (n - res) * A
			n = res
else:
	cost += (n - 1) * A
print(cost)


n = int(input())
k = int(input())
A = int(input())
if k == 1:
	print((n - 1) * A)
	exit()
B = int(input())
res = 0
x = n
k1 = (k - 1) * A
while x > 1:
	res += A * (x % k)
	x //= k
	if x:
		if B > x * k1:
			res += (x * k - 1) * A
			x = 1
		else:
			res += B
print(res - (1 - x) * A)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
c = 0
while n != 1:
	if k == 1 or k > n:
		c += (n - 1) * A
		break
	elif n % k != 0:
		c += n % k * A
		n -= n % k
	else:
		c += min(B, (n - n // k) * A)
		n = n // k
print(c)


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


n = int(input())
k = int(input())
a = int(input())
b = int(input())
ans = 0
if n >= k and k != 1:
	n1 = n
	while True:
		if n1 == 1:
			break
		if n1 < k:
			ans += (n1 - 1) * a
			break
		if n1 % k != 0:
			ans += n1 % k * a
			n1 -= n1 % k
		ans += min(b, (n1 - n1 // k) * a)
		n1 = n1 // k
	print(ans)
else:
	print((n - 1) * a)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
summ = 0
while n != 1:
	if k == 1 or n < k:
		summ += A * (n - 1)
		break
	if n % k != 0:
		times = n - n // k * k
		summ += A * times
		n -= times
	else:
		t2 = A * (n - n // k)
		if B < t2:
			summ += B
		else:
			summ += t2
		n = n // k
print(summ)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
x = n
cost = 0
while x != 1:
	if k == 1:
		cost += A * (x - 1)
		x = 1
	elif x % k == 0:
		x = x / k
		cost += min(B, A * (x * k - x))
	elif x % k == 1:
		x = x - 1
		cost += A
	else:
		cost += A * (x % k - 1)
		x = x - (x % k - 1)
print(int(cost))


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


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


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


n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1 or k > n:
	print((n - 1) * a)
else:
	count = 0
	while n > 1:
		if n % k == 0:
			s = min(b, (n - n // k) * a)
			n = n // k
		elif n > k:
			s = n % k * a
			n = n - n % k
		else:
			s = (n - 1) * a
			n = 1
		count += s
	print(count)


(n, k, a, b) = (int(input()), int(input()), int(input()), int(input()))
if k == 1:
	print(a * (n - 1))
else:
	ans = 0
	while n > 1:
		if n % k == 0:
			nw = n // k
			diff = n - nw
			if a * diff < b:
				ans += a * diff
			else:
				ans += b
			n = nw
		else:
			tosub = n % k
			ans += a * tosub
			n -= tosub
			if n == 0:
				ans -= a
	print(ans)


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())
price = 0
while x != 1:
	if k == 1:
		price = a * (x - 1)
		x = 1
	if x % k != 0:
		price += a * (x % k)
		price_bef = a * (x % k)
		x -= x % k
	elif x == 0:
		price -= a
		x = 1
	elif (x - x // k) * a < b:
		price += (x - x // k) * a
		x = x // k
	else:
		x = x // k
		price += b
print(price)


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


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


from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def MOD():
	return pow(10, 9) + 7

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
n = INI()
k = INI()
A = INI()
B = INI()
ans = 0
if k == 1:
	OPS(A * (n - 1))
else:
	while k <= n:
		if n % k == 0:
			ans += min(A * (n - n // k), B)
			n = n // k
		else:
			ans += n % k * A
			n -= n % k
	if n != 1:
		ans += (n - 1) * A
	OPS(ans)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
cost = 0
if k != 1:
	while n != 1:
		if n // k > 0:
			cost += (n - n // k * k) * A
			n = n // k * k
			if (n - n // k) * A < B:
				break
			n = n // k
			cost += B
		else:
			break
cost += (n - 1) * A
print(cost)


(n, k, a, b) = (int(input()), int(input()), int(input()), int(input()))
ans = 0
x = n
if k == 1:
	print((x - 1) * a)
	exit(0)
while x > 1:
	if x < k:
		ans += (x - 1) * a
		break
	if x == k:
		ans += min(b, (x - 1) * a)
		break
	tmp = x % k
	x -= tmp
	ans += tmp * a
	if x % k == 0:
		ans += min(b, (x - x / k) * a)
		x = x / k
print(int(ans))


n = int(input())
k = int(input())
A = int(input())
B = int(input())
x = n
ans = 0
if k == 1:
	ans = (n - k) * A
	print(ans)
else:
	while x > 1:
		if x % k == 0:
			div = int(x / k)
			temp1 = (x - div) * A
			temp2 = B
			if temp1 > temp2:
				x = int(x / k)
				ans += B
			else:
				x = int(x / k)
				ans += temp1
		else:
			val = int(x / k)
			if val != 0:
				val1 = val * k
				ans = ans + (x - val1) * A
				x = val1
			else:
				ans = ans + (x - 1) * A
				x = 1
	print(ans)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
ans = 0
if k == 1:
	ans = (n - 1) * a
else:
	while n != 1:
		if n % k == 0:
			nw = n // k
			len = 1
			x = min((n - nw) * a, b * len)
			ans += x
			n = nw
		else:
			ans += n % k * a
			n -= n % k
		if n == 0:
			ans -= a
			n = 1
print(ans)


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
	elif n % k != 0:
		t = n % k
		n -= t
		c += t * a
	elif b < (n - n // k) * a:
		n = n // k
		c += b
	else:
		c += a * (n - 1)
		n = 1
print(c)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
c = 0
if k > 1:
	while n // k * A * (k - 1) > B:
		c += n % k * A + B
		n //= k
c += (n - 1) * A
print(c)


from collections import Counter, defaultdict, deque
import heapq as hq
from itertools import count, islice
import math
import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
a = int(input())
b = int(input())
total = 0
if k == 1:
	print(a * (n - 1))
	exit()
while n != 1:
	rem = n % k
	if n < k:
		total += a * (rem - 1)
		break
	if rem:
		n -= rem
		total += rem * a
	else:
		total += min((n - n // k) * a, b)
		n //= k
print(total)


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


(n, k, a, b) = [int(input()) for i in range(4)]
r = 0
if k - 1:
	while n:
		(m, t) = divmod(n, k)
		r += t * a
		n -= t
		r += min(b, (n - m) * a)
		n = m
	r -= a
else:
	r += (n - 1) * a
print(r)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
if k == 1:
	if n > 1:
		res = (n - 1) * A
		print(res)
		exit(0)
	else:
		print(0)
		exit(0)
res = 0
while n > 1:
	if n < k:
		res += (n - 1) * A
		break
	r = n % k
	res += r * A
	n -= r
	p = (n - n // k) * A
	res += min(p, B)
	n = n // k
print(res)


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


GI = lambda : int(input())
GIS = lambda : map(int, input().split())
LGIS = lambda : list(GIS())

def main():
	n = GI()
	k = GI()
	A = GI()
	B = GI()
	x = n
	cost = 0
	if k == 1:
		return A * (x - 1)
	while x > 1:
		if x < k:
			cost += A * (x - 1)
			x = 1
			continue
		(div, mod) = divmod(x, k)
		if mod:
			cost += A * mod
			x -= mod
		else:
			cost += min((x - div) * A, B)
			x = div
	return cost
print(main())


n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1:
	cost = a * (n - 1)
	print(cost)
	exit()
ans = 0
cost = 0
while n > 1:
	cost += n % k * a
	n -= n % k
	if n > 1:
		aa = b
		bb = (n - n / k) * a
		cost += min(aa, bb)
		n = n // k
	elif n == 0:
		cost -= a
print(int(cost))


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


n = int(input())
k = int(input())
a = int(input())
b = int(input())
x = n
cost = 0
if k == 1:
	print(int((x - 1) * a))
	exit(0)
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 collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
n = iinput()
k = iinput()
a = iinput()
b = iinput()
if k == 1 or k > n:
	print(a * (n - 1))
else:
	ans = 0
	while n > 1:
		if n % k == 0:
			ans += min((n - n // k) * a, b)
			n //= k
		else:
			if k > n:
				ans -= a
			ans += n % k * a
			n -= n % k
	print(ans)


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


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


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


n = int(input())
k = int(input())
A = int(input())
B = int(input())
r = 0
if k == 1:
	r = n * A - A
while n > 1 and k > 1:
	if n < k:
		r += n * A - A
		break
	r += n % k * A
	n -= n % k
	r += min((n - n // k) * A, B)
	n = n // k
print(r)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
count = 0
if n == 1:
	print('0')
	exit(0)
while n // k * a * (k - 1) > b:
	count += n % k * a + b
	n = n // k
count += (n - 1) * a
print(count)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
x = n
c = 0
done = False
while x > 0:
	if done:
		c += x * A
		x = 0
	elif x % k != 0:
		c += x % k * A
		x -= x % k
	elif B < (x - x // k) * A:
		c += B
		x = x // k
	else:
		c += (x - x // k) * A
		x = x // k
		done = True
c -= A
print(c)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
if k == 1:
	print(A * (n - 1))
else:
	SUM = 0
	while n >= k:
		if n % k != 0:
			SUM += A * (n % k)
			n -= n % k
		else:
			X = A * (n - n // k)
			SUM += min(B, X)
			n //= k
	SUM += A * (n - 1)
	print(SUM)


(n, k, A, B) = [int(input()) for i in 'iiii']
s = 0
if k != 1:
	while n != 1 and n > 0:
		if n % k == 0:
			n = n // k
			s += min(n * (k - 1) * A, B)
		else:
			s += n % k * A
			n = n - n % k
			if n == 0:
				s -= A
				n = 1
	print(s)
else:
	print((n - 1) * A)


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


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


(n, k, A, B, sum) = (int(input()), int(input()), int(input()), int(input()), 0)
while n > 1:
	if n < k or k == 1:
		sum += A * (n - 1)
		break
	next = n // k
	if n % k == 0:
		sum += min(A * (n - next), B)
	else:
		next *= k
		sum += A * (n - next)
	n = next
print(sum)


RealAnswer = 1e+18

def KhelteThako(n, k, A, B, ans):
	global RealAnswer
	RealAnswer = min(RealAnswer, ans + (n - 1) * A)
	if n <= 1:
		if n == 1:
			RealAnswer = min(RealAnswer, ans)
			return
		return
	if n % k == 0:
		KhelteThako(n / k, k, A, B, ans + B)
	elif n > k:
		xx = n % k
		KhelteThako(n - xx, k, A, B, ans + xx * A)
	else:
		xx = n % k
		KhelteThako(n - xx + 1, k, A, B, ans + (xx - 1) * A)
n = int(input())
k = int(input())
A = int(input())
B = int(input())
ans = (n - 1) * A
if k == 1:
	print(ans)
else:
	KhelteThako(n, k, A, B, 0)
	print(min(ans, int(RealAnswer)))


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


inf = 4557430888798830399
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
s = 0
while x > 1:
	if x % k != 0 and x > k:
		s = s + A * (x % k)
		x = x - x % k
	elif x >= k:
		if x * (k - 1) // k * A > B:
			x = x // k
			s = s + B
		else:
			s = s + A * (x - 1)
			x = 1
	if x > 1 and x < k:
		s = s + (x - 1) * A
		x = 1
print(s)


(n, k, a, b) = (int(input()) for i in range(4))
(x, s) = (n, 0)
if k <= 1:
	print((x - 1) * a)
	quit()
while x != 1:
	if k > x:
		(s, x) = (s + (x - 1) * a, 1)
	elif x % k != 0:
		(s, x) = (s + x % k * a, x - x % k)
	elif x * (k - 1) // k * a > b:
		(s, x) = (s + b, x // k)
	else:
		(s, x) = (s + x * (k - 1) // k * a, x // k)
print(s)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
cost = 0
if n < k or k == 1:
	print((n - 1) * a)
else:
	while n > 1:
		r = n % k
		cost += r * a
		n -= r
		if n == 0:
			cost -= a
			break
		cost += min(a * (n - int(n / k)), b)
		n = int(n / k)
	print(cost)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
cost = 0
if k == 1:
	cost = (n - 1) * A
else:
	while n > 1:
		if n % k == 0:
			d = (k - 1) * n // k
			if d * A < B:
				n //= k
				cost += A * d
			else:
				n //= k
				cost += B
		elif n > k:
			cost += n % k * A
			n -= n % k
		else:
			cost += A * (n - 1)
			n = 1
print(cost)


def tanya(n, k, a, b):
	if k == 1:
		return (n - 1) * a
	s = 0
	while n > 1:
		if n % k != 0 and n < k:
			s += a * (n - 1)
			n -= n - 1
		elif n % k != 0:
			s += a * (n % k)
			n -= n % k
		elif n % k == 0:
			s += min(b, (n - n // k) * a)
			n = n // k
	return s
N = int(input())
K = int(input())
A = int(input())
B = int(input())
print(tanya(N, K, A, B))


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


n = int(input())
k = int(input())
a = int(input())
b = int(input())
coins = 0
while n > 1:
	if n < k or k == 1:
		coins += a * (n - 1)
		n = 1
	elif n == k:
		coins += min(a * (n - 1), b)
		n = 1
	elif n % k == 0:
		if a * (n - n // k) < b:
			coins += a * (n - n // k)
			n //= k
		else:
			coins += b
			n //= k
	else:
		coins += a * (n % k)
		n -= n % k
print(coins)


(n, k, a, b) = [int(input()) for _ in range(4)]
if k == 1:
	print((n - 1) * a)
	exit(0)
(t, c) = (n, 0)
while t > 1:
	m = t % k
	if m:
		if t < k:
			m -= 1
		c += m * a
		t -= m
	else:
		c += min(a * (k - 1) * t // k, b)
		t //= k
print(c)


from collections import defaultdict
(n, k, A, B) = (int(input()), int(input()), int(input()), int(input()))
if k == 1:
	print(A * (n - 1))
else:
	numbers = {n: 0}
	digits = []
	while n > 0:
		digits.append(n % k)
		n = n // k
	P = len(digits)
	for i in range(P - 1):
		newnumbers = defaultdict(list)
		for (m, cost) in numbers.items():
			newnumbers[m // k].append(cost + m % k * A + B)
			lowermax = k ** (P - i - 1) - 1
			newnumbers[lowermax].append(cost + (m - lowermax) * A)
		numbers = {n: min(costs) for (n, costs) in newnumbers.items()}
	answer = min([cost + (n - 1) * A for (n, cost) in numbers.items()])
	print(answer)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
anw = 0
if k == 1:
	print(a * (n - 1))
	exit(0)
while n > 1:
	if n % k != 0:
		if n < k:
			n -= 1
		anw += a * (n % k)
		n -= n % k
	else:
		toMinus = (n - n // k) * a
		anw += min(toMinus, b)
		n //= k
print(anw)


def f(n, k, A, B):
	if k == 1:
		return (n - 1) * A
	if n < k:
		return A * (n - 1)
	elif n % k == 0:
		return min((n - 1) * A, B + f(n // k, k, A, B))
	else:
		return n % k * A + f(n - n % k, k, A, B)
n = int(input())
k = int(input())
A = int(input())
B = int(input())
print(f(n, k, A, B))


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


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


n = int(input())
k = int(input())
A = int(input())
B = int(input())
total = 0
flag = True
while n > 1:
	if n < k:
		total += (n - 1) * A
		break
	if n % k == 0:
		new = n / k
		if flag:
			if B <= A * (n - new):
				total += B
				n = new
			else:
				flag = False
		if not flag:
			total += (n - 1) * A
			n = 1
	else:
		temp = n - n // k * k
		total += temp * A
		n -= temp
print(int(total))


def dp(x, k, a, b):
	if x < k or k == 1:
		return (x - 1) * a
	if x % k == 0:
		return dp(x // k, k, a, b) + min(b, a * (x - x // k))
	else:
		return dp(x - x % k, k, a, b) + x % k * a
n = int(input())
k = int(input())
a = int(input())
b = int(input())
print(dp(n, k, a, b))


import time
import math
debug = False
nFiles = int(input())
kCommand2 = int(input())
Cost1 = int(input())
Cost2 = int(input())
if debug:
	print('---')
begin = time.time()
TotalCost = 0
if kCommand2 > 1:
	while nFiles > 1:
		if nFiles % kCommand2 != 0:
			sub = min(nFiles % kCommand2, nFiles - 1)
			TotalCost += Cost1 * sub
			nFiles -= sub
			if debug:
				print('1 nFiles ', nFiles)
		else:
			nFilesNew = nFiles // kCommand2
			TotalCost += min(Cost2, Cost1 * (nFiles - nFilesNew))
			nFiles = nFilesNew
			if debug:
				print('2 nFiles ', nFiles)
else:
	TotalCost = (nFiles - 1) * Cost1
if debug:
	print(time.time() - begin)
if debug:
	print('---')
print(TotalCost)


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


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


n = int(input())
k = int(input())
A = int(input())
B = int(input())
cost = 0
if k == 1:
	cost += (n - 1) * A
else:
	while n > 1:
		r = n % k
		q = n // k
		if n < k:
			cost += (n - 1) * A
			n = 1
		elif r != 0:
			cost += r * A
			n -= r
		else:
			cost += min(B, (n - q) * A)
			n = q
print(cost)


from math import *
n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1:
	print(a * (n - 1))
else:
	ans = 0
	while n >= k:
		ans += n % k * a
		n -= n % k
		dif = n - n / k
		if dif * a <= b:
			ans += dif * a
		else:
			ans += b
		n = n / k
	ans += (n - 1) * a
	print(int(ans))


(n, k, A, B) = [int(input()) for _ in range(4)]
s = 0
if k == 1:
	print(A * (n - 1))
	exit()
while n > 1:
	t = n % k
	d = n // k
	if not d:
		s += (n - 1) * A
		print(s)
		exit()
	s += A * t if t else min(A * (n - d), B)
	n = k * d if t else d
print(s)


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


copys = int(input())
k = int(input())
A = int(input())
B = int(input())
time = 0
while copys != 1:
	b = copys % k
	if b != 0 and copys >= k and (k != 1):
		time += A * b
		copys -= b
	elif b == copys or k == 1:
		time += A * (copys - 1)
		copys = 1
		break
	elif b == 0 and B >= A * (copys - copys // k) and (k != 1):
		time += A * (copys - copys // k)
		copys //= k
	if copys != 1 and b == 0 and (B < A * (copys - copys // k)) and (k != 1):
		time += B
		copys //= k
print(time)


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


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


(n, k, a, b) = [int(input()) for i in range(4)]
sm = 0
x = n
if k == 1:
	print((x - 1) * a)
	exit()
while x != 1:
	if x % k == 0:
		a1 = x // k
		sm += min(b, (x - a1) * a)
		x //= k
	else:
		if x < k:
			sm += (x - 1) * a
			break
		sm += a * (x % k)
		x = x // k * k
print(sm)


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


def main():
	(n, k, a, b) = (int(input()) for _ in 'nkab')
	r = 0
	if k > 1:
		while n >= k:
			r += n % k * a
			n //= k
			r += min(b, n * (k - 1) * a)
	print(r + (n - 1) * a)
main()


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


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


n = int(input())
k = int(input())
a = int(input())
b = int(input())
c = 0
if k == 1:
	c = (n - 1) * a
else:
	while not n == 1:
		if not n % k == 0:
			c += n % k * a
			n = n - n % k
		elif n < k:
			c += (n - 1) * a
			n = 1
		else:
			d1 = n / k
			c1 = b
			c2 = (n - d1) * a
			if c1 < c2:
				c += c1
			else:
				c += c2
			n = d1
print(int(c))


n = int(input())
k = int(input())
a = int(input())
b = int(input())
x = n
ans = 0
while x > 1:
	if x % k == 0 and k != 1:
		case1 = b
		case2 = (x - x // k) * a
		ans += min(case1, case2)
		x = x // k
	elif x >= k and k != 1:
		ans += x % k * a
		x -= x % k
	else:
		ans += (x - 1) * a
		x = 1
print(ans)


import sys
n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1:
	print((n - 1) * a)
	sys.exit()
s = 0
while n > 1:
	if n % k == 0:
		d = n - n // k
		if b > a * d:
			n -= d
			s += a * d
		else:
			n //= k
			s += b
	elif n // k == 0:
		s += (n % k - 1) * a
		n -= n % k - 1
	else:
		s += n % k * a
		n -= n % k
print(s)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
p = 0
if k == 1:
	p = A * (n - 1)
else:
	while n >= k:
		p += A * (n % k)
		n -= n % k
		p += min(B, A * (n - n // k))
		n = n // k
	p += A * (n - 1)
print(p)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
s = 0
while n != 1:
	if k > n or k == 1:
		s += A * (n - 1)
		break
	if n % k != 0:
		s += A * (n % k)
		n = n - n % k
	else:
		nxt = n // k
		if (n - nxt) * A < B:
			s += (n - nxt) * A
		else:
			s += B
		n = nxt
print(int(s))


import sys
n = int(input())
k = int(input())
A = int(input())
B = int(input())
x = n
cst = 0
if k == 1:
	print((x - 1) * A)
	sys.exit(0)
while x != 1:
	if x % k == 0:
		cst += min((x - x // k) * A, B)
		x = x // k
	elif x < k:
		cst += (x - 1) * A
		x = 1
	else:
		cst += x % k * A
		x -= x % k
print(cst)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
cn = 0
if k == 1:
	print((n - 1) * a)
	exit(0)
while n >= 1:
	x = n % k
	cn += a * x
	n -= x
	if n == 0:
		cn -= a
		break
	nn = n // k
	cn += min(b, (n - nn) * a)
	n = nn
print(cn)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
coin = 0
if k == 1:
	print(int(A * (n - 1)))
else:
	while n > 1:
		if n % k == 0:
			cur = (n - n / k) * A
			if cur > B:
				coin += B
			else:
				coin += cur
			n /= k
		else:
			cur = n % k * A
			n -= n % k
			coin += cur
			if n == 0:
				coin -= A
	print(int(coin))


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


n = int(input())
k = int(input())
A = int(input())
B = int(input())
c = 0
if k > n or k == 1:
	c = (n - 1) * A
	n = 1
while n > 1:
	if n % k != 0:
		if n > k:
			c += A * (n % k)
			n -= n % k
		else:
			c += A
			n -= 1
	else:
		if (n - n / k) * A < B:
			c += (n - n / k) * A
		else:
			c += B
		n /= k
print(str(int(c)))


import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
a = int(input())
b = int(input())
ans = 0
if k == 1:
	print((n - 1) * a)
	exit()
while n > 1:
	if n < k:
		ans += (n - 1) * a
		break
	if n % k != 0:
		ans += n % k * a
		n -= n % k
	else:
		while n % k == 0 and n > 1:
			temp = n // k
			if (n - temp) * a >= b:
				ans += b
			else:
				ans += (n - temp) * a
			n //= k
print(ans)


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)


a = [0] * 4
for i in range(4):
	a[i] = int(input())
cost = 0
while a[0] > 1:
	if a[0] % a[1] == 0:
		if a[1] == 1:
			cost += (a[0] - 1) * a[2]
			a[0] = 1
		elif a[3] <= (a[0] - a[0] // a[1]) * a[2]:
			a[0] = a[0] // a[1]
			cost += a[3]
		else:
			cost += (a[0] - a[0] // a[1]) * a[2]
			a[0] = a[0] // a[1]
	elif a[0] % a[1] == a[0]:
		cost += (a[0] - 1) * a[2]
		a[0] = 1
	else:
		cost += (a[0] - a[1] * (a[0] // a[1])) * a[2]
		a[0] = a[1] * (a[0] // a[1])
print(cost)


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


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


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())
if k == 1:
	print((n - 1) * A)
	exit()
s = 0
while n > 1:
	if n < k:
		s += A * (n - 1)
		break
	r = n % k
	if r > 0:
		s += r * A
		n -= r
	else:
		m = n // k
		s += min((n - m) * A, B)
		n = m
print(s)


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : list(map(int, input().split()))
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n = ii()
k = ii()
A = ii()
B = ii()
if k == 1:
	print((n - 1) * A)
	exit()
cost = 0
while n > 1:
	if n % k:
		if n == n % k:
			cost += (n % k - 1) * A
			n = 1
		else:
			cost += n % k * A
			n -= n % k
	else:
		cost += min(B, (n - n // k) * A)
		n //= k
print(cost)


from sys import stdin, stdout

def rint():
	return map(int, stdin.readline().split())
n = int(input())
k = int(input())
A = int(input())
B = int(input())
cost = 0
p = n % k
if k == 1:
	print((n - 1) * A)
	exit()
res = n
while res != 1:
	if res < k:
		cost += (res - 1) * A
		break
	if res % k:
		cost += res % k * A
		res = res - res % k
		continue
	if B < (res - res // k) * A:
		cost += B
	else:
		cost += (res - res // k) * A
	res = res // k
print(cost)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
sum = 0
while n != 1:
	if k > 1:
		if n % k == 0:
			f = n // k
			h = n - f
			n = f
			sum += min(h * a, b)
		elif n > k:
			sum += a * (n % k)
			n = n - n % k
		else:
			sum += a * (n - 1)
			n = 1
	else:
		sum += (n - 1) * a
		n = 1
print(sum)


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

def test(i):
	if i == 1:
		return 0
	else:
		res = A * (i - 1)
		if i >= k:
			res = min(res, A * (i % k) + B + test(i // k))
		return res
if k == 1:
	print((x - 1) * A)
else:
	print(test(x))


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


def solve():
	n = int(input())
	k = int(input())
	a = int(input())
	b = int(input())
	c = n
	ans = 0
	if k > 1:
		while c != 1 and c > 0:
			if c % k != 0:
				if c > k:
					ans += c % k * a
					c = c - c % k
				else:
					ans += (c % k - 1) * a
					c = c - c % k
			elif b <= (c - c // k) * a:
				c = c // k
				ans += b
			else:
				p = c - c // k
				ans += p * a
				c = c // k
	else:
		ans = a * (n - 1)
	print(ans)
test_case = 1
while test_case:
	solve()
	test_case -= 1


x = int(input())
k = int(input())
A = int(input())
B = int(input())
p = 0
while x > 1:
	if k == 1:
		print(A * (x - 1))
		exit()
	if x % k == 0:
		p += min(B, (x - x / k) * A)
		x = x / k
	elif x - x % k == 0:
		p += (x % k - 1) * A
		print(int(p))
		exit()
	else:
		p += x % k * A
		x -= x % k
print(int(p))


n = int(input())
k = int(input())
A = int(input())
B = int(input())
zen = 0
if k == 1:
	print(A * (n - 1))
	exit(0)
while n >= k:
	zen += n % k * A
	n -= n % k
	if B <= (n - n // k) * A:
		zen += B
		n //= k
	else:
		zen += (n - n // k) * A
		n //= k
zen += A * (n - 1)
print(zen)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
mans = 0
if k == 1:
	print((n - 1) * A)
else:
	while n != 1:
		ans = 0
		if n % k == 0:
			ans = n / k
			mans += min((n - ans) * A, B)
			n = int(n / k)
		else:
			x = n - n % k
			if x == 0:
				mans += (n - 1) * A
				n = 1
			else:
				mans += (n - x) * A
				n = x
	print(int(mans))


(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
		elif 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)


def run():
	(n, k, a, b) = (int(input()), int(input()), int(input()), int(input()))
	if n == 1:
		print(0)
		return
	if k == 1:
		print((n - 1) * a)
		return
	r = 0
	while True:
		if n < k:
			print(r + (n - 1) * a)
			return
		rem = n % k
		if rem != 0:
			r += a * rem
			n -= rem
			continue
		decr = n - n // k
		r += min(b, decr * a)
		n = n // k
run()


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
	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())
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
res = res + (n - 1) * a + ost
print(res)


import sys
inf = float('inf')
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
(mod, MOD) = (1000000007, 998244353)
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1:
	print((n - 1) * a)
	exit(0)
total = 0
while n > 1:
	if n % k != 0 and n < k:
		total = total + a * (n - 1)
		n -= n - 1
	elif n % k != 0:
		total += a * (n % k)
		n -= n % k
	elif n % k == 0:
		total += min(b, (n - n // k) * a)
		n = n // k
print(total)


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


from os import path
import sys, time
mod = int(1000000000.0 + 7)
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, permutations
from string import ascii_lowercase, ascii_uppercase
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
I = lambda : int(sys.stdin.buffer.readline())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
grid = lambda r: [lint() for i in range(r)]
localsys = 0
start_time = time.time()
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)

def ceill(n, x):
	return (n + x - 1) // x
T = 0

def solve():
	(n, k, a, b) = (I(), I(), I(), I())
	ans = 0
	if k == 1:
		ans += (n - 1) * a
		n = 1
	while n > 1:
		if n % k:
			if n < k:
				ans += (n - 1) * a
				break
			ans += (n - n // k * k) * a
			n = n // k * k
		else:
			y = (n - n // k) * a
			t = b if b <= y else y
			ans += t
			n //= k
	print(ans)

def run():
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
run()
T = I() if T else 1
for _ in range(T):
	solve()
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


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


(n, k, a, b) = (int(input()), int(input()), int(input()), int(input()))
s = 0
while n > 1:
	if n < k or k == 1:
		s += (n - 1) * a
		n = 1
		continue
	if n % k == 0:
		if b < a * (n - n // k):
			s += b
		else:
			s += a * (n - n // k)
		n //= k
	else:
		s += n % k * a
		n -= n % k
print(int(s))


(x, k, a, b) = (int(input()), int(input()), int(input()), int(input()))
res = 0
if k == 1:
	print(a * (x - 1))
	from sys import exit
	exit()
while x > 1:
	mod = x % k
	if mod == 0:
		y = x // k
		c = a * (x - y)
		if b > c:
			res += c
		else:
			res += b
		x = y
	else:
		res += a * mod
		x -= mod
if x == 0:
	res -= a
print(res)


import sys
n = int(input())
k = int(input())
a = int(input())
b = int(input())
coin = 0
if n == 1:
	print('0')
	sys.exit()
if k == 1:
	print((n - 1) * a)
	sys.exit()
sum = 0
while n != 1:
	if n < k:
		sum = sum + (n - 1) * a
		break
	if n % k != 0:
		sum = sum + a * (n % k)
		n = n - n % k
	else:
		i = n - n // k
		if b > i * a:
			n = n // k
			sum = sum + i * a
		else:
			n = n // k
			sum = sum + b
print(sum)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
cost = 0
if k == 1:
	print(A * (n - 1))
else:
	while n != 1:
		if n % k != 0:
			shift = n % k if n > k else n - 1
			tcost = shift * A
			n -= shift
		else:
			tcost = min(B, A * (n - n // k))
			n //= k
		cost += tcost
	print(cost)


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


import sys
n = int(input())
divisor = int(input())
price_sub = int(input())
price_div = int(input())
x = n
cost = 0
if divisor == 1:
	cost += (x - 1) * price_sub
	print(int(cost))
	sys.exit(0)
num_subs = divisor - 1
while x > 1:
	if x % divisor != 0:
		mod = x % divisor
		cost += price_sub * mod
		x -= mod
		if x < 1:
			cost -= price_sub
		continue
	points = x - x // divisor
	if price_div < points * price_sub:
		cost += price_div
		x = x // divisor
		continue
	cost += (x - 1) * price_sub
	print(int(cost))
	sys.exit(0)
print(int(cost))


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
	elif (x - x // k) * a >= b:
		c += b
		x = x // k
	else:
		c += (x - 1) * a
		x = 1
print(c)


import math

class CodeforcesTask940BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.k = 0
		self.a = 0
		self.b = 0

	def read_input(self):
		self.n = int(input())
		self.k = int(input())
		self.a = int(input())
		self.b = int(input())

	def process_task(self):
		if self.n < self.k:
			cost = (self.n - 1) * self.a
		elif self.k == 1:
			cost = (self.n - 1) * self.a
		else:
			cost = 0
			x = self.n
			while x > 1:
				if x >= self.k:
					rest = x % self.k
					if rest:
						cost += rest * self.a
						x -= rest
					else:
						cost += min(self.b, (x - x // self.k) * self.a)
						x //= self.k
				else:
					cost += (x - 1) * self.a
					x = 1
		self.result = str(cost)

	def get_result(self):
		return self.result
Solution = CodeforcesTask940BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


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(o)
main()


def solve():
	n = int(input())
	k = int(input())
	A = int(input())
	B = int(input())
	if k == 1:
		print((n - 1) * A)
		return
	cost = 0
	x = n
	while True:
		if x == 1:
			print(cost)
			return
		r = x % k
		if r != 0:
			if x > k:
				cost += A * r
				x -= r
			else:
				cost += A * (r - 1)
				x -= r - 1
		else:
			tmp = x // k
			if A * (x - tmp) <= B:
				cost += A * (x - tmp)
				x -= x - tmp
			else:
				cost += B
				x //= k
solve()


from functools import *
from time import time

def measure_time(fun):

	def wrapper(*args, **kwargs):
		begin = time()
		rv = fun(*args, **kwargs)
		end = time()
		print(end - begin)
		return rv
	return wrapper

def our_cache(func):
	memo = [-1] * (max + 1)

	@wraps(func)
	def wrapper(arg):
		if memo[arg] == -1:
			memo[arg] = func(arg)
		return memo[arg]
	return wrapper

def main():
	(n, k, A, B) = (int(input()), int(input()), int(input()), int(input()))
	if k == 1:
		print(A * (n - 1))
		return
	op = 0
	while n > 1:
		if n % k == 0:
			op += A * (n - n // k) if B > A * (n - n // k) else B
			n //= k
		else:
			x = n % k if n > k else n - 1
			op += x * A
			n -= x
	print(op)
main()


n = int(input())
k = int(input())
A = int(input())
B = int(input())
ans = 0
if n == 1:
	print(0)
elif k == 1:
	print((n - 1) * A)
else:
	while True:
		if n == 1:
			print(ans)
			break
		else:
			ost = n % k
			if ost == 0:
				s = A * (n - n // k)
				ans += min(s, B)
				n = n // k
			elif n - ost > 0:
				ans += A * ost
				n = n - ost
			else:
				n = 1
				ans += (ost - 1) * A


n = int(input())
k = int(input())
A = int(input())
B = int(input())
x = n
cost = 0
worth_div = True
while x > 1:
	if x % k == 0 and worth_div:
		worth_div = (x - int(x / k)) * A > B
		if worth_div:
			cost += B
			x = int(x / k)
		else:
			cost += A * (x - 1)
			x = 1
	elif x % k == 0 or x < k:
		cost += A * (x - 1)
		x = 1
	else:
		cost += x % k * A
		x -= x % k
print(cost)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
cost = 0
if k > 1:
	while n > 1:
		if n >= k and n % k == 0:
			q = n // k
			cost += min((n - q) * a, b)
			n = q
		elif n >= k and n % k != 0:
			q = n // k
			l = q * k
			cost += (n - l) * a
			n = l
		else:
			cost += (n - 1) * a
			n = 1
cost += (n - 1) * a
print(cost)


n = int(input().strip())
k = int(input().strip())
a = int(input().strip())
b = int(input().strip())
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:
			m = n % k
			n -= m
			cost += m * a
			if n == 0:
				n = 1
				cost -= a
print(cost)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
if k == 1:
	print((n - 1) * A)
else:
	ct = 0
	while n >= k:
		q = n % k
		n -= q
		ct += q * A
		tg = n // k
		ct += min(B, (n - tg) * A)
		n = tg
	ct += (n - 1) * A
	print(ct)


import sys
import heapq
from math import ceil
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
n = int(ri())
k = int(ri())
a = int(ri())
b = int(ri())
cost = 0
if k == 1:
	print((n - 1) * a)
	exit()
while n != 1:
	if n % k == 0:
		if b > (n - n // k) * a:
			cost += (n - n // k) * a
			n = n // k
		else:
			cost += b
			n = n // k
	elif n < k:
		cost += (n - 1) * a
		n = 1
	else:
		cost += a * (n % k)
		n -= n % k
print(cost)


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


def solve(n, k, a, b):
	ans = 0
	if k == 1:
		print((n - 1) * a)
		return
	while n != 1:
		if n < k:
			ans += (n - 1) * a
			n = 1
		elif n % k != 0:
			ans += n % k * a
			n -= n % k
		elif b < (n - n // k) * a:
			n /= k
			ans += b
		else:
			ans += (n - n // k) * a
			n /= k
	print(int(ans))
n = int(input())
k = int(input())
a = int(input())
b = int(input())
solve(n, k, a, b)


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


n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1 or k > n:
	print((n - 1) * a)
else:
	x = n
	coin = 0
	while x != 1:
		if x < k:
			coin += (x - 1) * a
			x = 1
		elif x % k != 0:
			r = x % k
			coin += r * a
			x -= r
		elif x % k == 0:
			p = x // k
			if b <= (x - p) * a:
				coin += b
				x = p
			else:
				coin += a * (x - p)
				x = p
	print(coin)


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
input = stdin.readline
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
mi = lambda : map(int, input().split())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
mati = lambda r: [li() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def solve():
	n = ii()
	k = ii()
	a = ii()
	b = ii()
	ans = 0
	if k == 1:
		ans = a * (n - 1)
	else:
		while n != 1:
			if n % k == 0:
				if (n - n // k) * a < b:
					ans += a * (n - n // k)
				else:
					ans += b
				n //= k
			elif n > k:
				ans += n % k * a
				n -= n % k
			else:
				ans += (n - 1) * a
				n = 1
	print(ans)
for _ in range(1):
	solve()


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

def func(n, k, a, b):
	if n == 1:
		return 0
	if k == 1:
		return a * (n - 1)
	if n < k:
		return (n - 1) * a
	elif n % k != 0:
		return n % k * a + func(n - n % k, k, a, b)
	else:
		return min((n - n // k) * a, b) + func(n // k, k, a, b)
print(func(n, k, a, b))


n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1:
	print((n - 1) * a)
	exit(0)
cost = 0
while n > k:
	rem = n % k
	cost += rem * a
	n -= rem
	cost_a = (n - n // k) * a
	n = n // k
	cost += min(cost_a, b)
if n == k:
	cost += min((n - 1) * a, b)
else:
	cost += (n - 1) * a
print(cost)


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1:
	print(a * (n - 1))
else:
	spent = 0
	while n > 1:
		if n % k:
			if n > k:
				spent += a * (n % k)
				h = n % k
				n -= h
			else:
				spent += a * (n - 1)
				n = 1
		else:
			spent += min(b, (n - n // k) * a)
			n = n // k
	print(spent)


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


(n, k, A, B, v) = (int(input()), int(input()), int(input()), int(input()), 0)
while n > 1:
	if k == 1 or n < k:
		v += A * (n - 1)
		n = 1
	elif n % k:
		v += A * (n % k)
		n -= n % k
	else:
		v += min(A * (n - n // k), B)
		n //= k
print(v)


def main():
	n = int(input())
	k = int(input())
	A = int(input())
	B = int(input())
	cost = 0
	if k == 1:
		print((n - 1) * A)
		exit(0)
	if n == 1:
		print(0)
		exit(0)
	while n > 1:
		if n % k != 0:
			mul = n - k * (n // k)
			cost += A * mul
			n -= mul
		else:
			subCost = A * (n - n // k)
			cost += min(subCost, B)
			n //= k
	if n == 0:
		cost -= A
	print(cost)
main()


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


n = int(input())
k = int(input())
a = int(input())
b = int(input())
l = []
s = 0
if k == 1:
	print(a * (n - 1))
else:
	while n != 1:
		if n < k and n != 1:
			s += (n - 1) * a
			n = 1
		elif n % k != 0:
			s += n % k * a
			n -= n % k
		else:
			s += min((n - n / k) * a, b)
			n = n // k
	print(int(s))


n = int(input())
k = int(input())
A = int(input())
B = int(input())
result = 0
while n != 1:
	steps = n % k
	if steps != 0:
		n -= steps
		result += A * steps
	else:
		next = n // k
		if (n - next) * A > B:
			n = next
			result += B
		else:
			break
if n != 1:
	result += A * (n - 1)
print(result)


n = int(input())
k = int(input())
A = int(input())
B = int(input())
mi = 0
if k == 1:
	print((n - 1) * A)
	exit()
while n != 1:
	if n % k != 0:
		mi += n % k * A
		n -= n % k
		if n <= 0:
			mi -= A * abs(n - 1)
			n = 1
	else:
		p = n
		n /= k
		mi += min(B, (p - n) * A)
print(int(mi))


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())

def fun(n, k, a, b):
	if k == 1:
		return (n - 1) * a
	if n == 1:
		return 0
	if n < k:
		return (n - 1) * a
	return min(n % k * a + fun(n // k, k, a, b) + b, (n - 1) * a)
print(fun(n, k, a, b))


import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
N = int(input())
K = int(input())
A = int(input())
B = int(input())
if K == 1:
	print((N - 1) * A)
else:
	ans = 0
	x = N
	while x > 1:
		if x < K:
			ans += (x - 1) * A
			break
		elif x % K != 0:
			new_x = x // K * K
			ans += (x - new_x) * A
			x = new_x
		else:
			new_x = x // K
			cost1 = B
			cost2 = (x - new_x) * A
			ans += min(cost1, cost2)
			x = new_x
	print(ans)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
c = 0
while n != 1:
	if n % k == 0 and k != 1:
		v = n // k
		d = (n - v) * a
		if d < b:
			n = v
			c += d
		else:
			n = n // k
			c += b
	elif k == 1:
		var = (n - 1) * a
		n = 1
		c += var
	elif n > k:
		f = n % k
		n -= f
		c += a * f
	else:
		ans = (n - 1) * a
		n = 1
		c += ans
print(c)


n = int(input())
k = int(input())
a = int(input())
b = int(input())
if n == 1:
	print(0)
	exit()
if k == 1:
	print((n - 1) * a)
	exit()
ans = 0
while n != 1:
	(q, r) = divmod(n, k)
	if q == 0:
		ans += (r - 1) * a
		n = 1
	elif r == 0:
		ans += min(b, (n - n // k) * a)
		n //= k
	else:
		ans += r * a
		ans += min(b, (n - r - n // k) * a)
		n //= k
print(ans)


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)


import math
n = int(input())
k = int(input())
A = int(input())
B = int(input())
answer = 0
rest = math.inf
x = n
while x != 1:
	if k == 1 or x < k:
		answer += A * (x - 1)
		x = 1
	else:
		temp = answer
		res1 = answer + A * (x - 1)
		res2 = answer + A * (x % k) + B
		x -= x % k
		x //= k
		if res1 < res2:
			x = 1
			answer = res1
		else:
			rest = res1 if res1 < rest else rest
			answer = res2
print(answer if answer < rest else rest)


(n, k, A, B) = (int(input()) for i in range(4))
cost = 0
if k == 1:
	print((n - 1) * A)
else:
	while n > 1:
		if n % k != 0:
			m = n % k
			n -= m
			cost += A * (m - 1) if n < 1 else A * m
		else:
			m = n // k
			cost += (n - m) * A if (n - m) * A < B else B
			n = m
	print(cost)


import sys
n = int(sys.stdin.readline().strip())
k = int(sys.stdin.readline().strip())
A = int(sys.stdin.readline().strip())
B = int(sys.stdin.readline().strip())
optimalPrice = 0
if k == 1:
	optimalPrice = A * (n - 1)
else:
	while n > 1:
		if n % k == 0:
			optimalPrice += min(B, A * (n - n // k))
			n //= k
		elif n < k:
			optimalPrice += A * (n - 1)
			n = 1
		else:
			optimalPrice += A * (n % k)
			n -= n % k
print(optimalPrice)


n = int(input())
div = int(input())
minusCost = int(input())
divCost = int(int(input()))
if div == 1:
	print((n - 1) * minusCost)
	exit()
ret = 0
cur = n
while cur > 1:
	if cur < div:
		ret += (cur - 1) * minusCost
		cur = 1
	elif cur % div != 0:
		ret += cur % div * minusCost
		cur -= cur % div
	else:
		ret += min(divCost, (cur - cur // div) * minusCost)
		cur //= div
print(ret)


import math
n = int(input())
k = int(input())
a = int(input())
b = int(input())
l = []
a1 = a * (n - 1)
if k != 1 and k <= n:
	a2 = 0
	while n != 1:
		if n % k == 0:
			n = n // k
			a2 += b
			l.append(a2 + (n - 1) * a)
		elif n > k:
			p = n % k
			a2 += p * a
			n -= p
			l.append(a2 + (n - 1) * a)
		else:
			a2 += (n - 1) * a
			n = 1
	print(min(a1, min(l), a2))
else:
	print(a1)


class COL:

	def main(self):
		n = int(input())
		k = int(input())
		a = int(input())
		b = int(input())
		x = n
		count = 0
		if k == 1:
			print(str((x - 1) * a))
			return
		while x > 1:
			if x < k:
				count = count + a * (x - 1)
				break
			if x % k == 0:
				if (x - x / k) * a < b:
					count = count + (x - x / k) * a
				else:
					count = count + b
				x = x / k
			else:
				count = count + x % k * a
				x = x - x % k
		print(str(int(count)))
c = COL()
c.main()