Problem:
 Score : 400 points    Problem Statement You start with the number 0 and you want to reach the number N .  You can change the number, paying a certain amount of coins, with the following operations:   Multiply the number by 2 , paying A coins.  Multiply the number by 3 , paying B coins.  Multiply the number by 5 , paying C coins.  Increase or decrease the number by 1 , paying D coins.   You can perform these operations in arbitrary order and an arbitrary number of times.  What is the minimum number of coins you need to reach N ?  You have to solve T testcases.      Constraints  1 \le T \le 10  1 \le N \le 10^{18}  1 \le A, B, C, D \le 10^9  All numbers N, A, B, C, D are integers.         Input The input is given from Standard Input. The first line of the input is  T   Then, T lines follow describing the T testcases.
Each of the T lines has the format  N  A  B  C  D       Output For each testcase, print the answer on Standard Output followed by a newline.        Sample Input 1 5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321      Sample Output 1 20
19
26
3821859835
23441258666  For the first testcase, a sequence of moves that achieves the minimum cost of 20 is:   Initially x = 0 .  Pay 8 to increase by 1 ( x = 1 ).  Pay 1 to multiply by 2 ( x = 2 ).  Pay 1 to multiply by 2 ( x = 4 ).  Pay 2 to multiply by 3 ( x = 12 ).  Pay 8 to decrease by 1 ( x = 11 ).   For the second testcase, a sequence of moves that achieves the minimum cost of 19 is:   Initially x = 0 .  Pay 8 to increase by 1 ( x = 1 ).  Pay 1 to multiply by 2 ( x = 2 ).  Pay 2 to multiply by 5 ( x = 10 ).  Pay 8 to increase by 1 ( x = 11 ).

Solution (Python):



times = int(input())
x = []
for t in range(times):
    x.append(list(map(int, input().split())))


def f(n):
    if n == 0:
        return 0
    if n == 1:
        return d
    if n in dic:
        return dic[n]

    if n%2 == 0:
        n2 = f(n // 2) + a
    elif n%2 == 1:
        n2 = min(f((n-1) // 2) + d, f((n+1) // 2) + d) + a

    if n%3 == 0:
        n3 = f(n // 3) + b
    elif n%3 == 1:
        n3 = min(f((n-1) // 3) + d, f((n+2) // 3) + 2*d) + b
    elif n%3 == 2:
        n3 = min(f((n-2) // 3) + 2*d, f((n+1) // 3) + d) + b

    if n%5 == 0:
        n5 = f(n // 5) + c
    elif n%5 == 1:
        n5 = min(f((n-1) // 5) + d, f((n+4) // 5) + 4*d) + c
    elif n%5 == 2:
        n5 = min(f((n-2) // 5) + 2*d, f((n+3) // 5) + 3*d) + c
    elif n%5 == 3:
        n5 = min(f((n-3) // 5) + 3*d, f((n+2) // 5) + 2*d) + c
    elif n%5 == 4:
        n5 = min(f((n-4) // 5) + 4*d, f((n+1) // 5) + d) + c

    Y = min(n2, n3, n5, n*d)
    dic[n] = Y
    return Y


for t in range(times):
    n, a, b, c, d = x[t][0], x[t][1], x[t][2], x[t][3], x[t][4]
    dic = {}
    print(f(n))

Solution (Python):


def main():
    from heapq import heappush, heappop

    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())

        h = [(0, N)]  
        checked = set()

        ans = N * D + 1
        while h:
            cost, x = heappop(h)
            if cost >= ans: continue
            if x in checked: continue
            checked.add(x)

            
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                
                
                
                nx, r = divmod(x, d)
                if nx not in checked:
                    heappush(h, (cost + r * D + c, nx))
                if (r > 0) and ((nx + 1) not in checked):
                    heappush(h, (cost + (d - r) * D + c, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


def main():
    from heapq import heappush, heappop

    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())

        h = [(0, N)]  
        checked = set()

        ans = N * D + 1
        while h:
            cost, x = heappop(h)
            if cost >= ans: continue
            if x in checked: continue
            checked.add(x)

            
            if ans > cost + x * D:
                ans = cost + x * D

            for d, c in ((2, A), (3, B), (5, C)):
                
                
                
                nx, r = divmod(x, d)
                if nx not in checked:
                    heappush(h, (cost + r * D + c, nx))
                if (r > 0) and ((nx + 1) not in checked):
                    heappush(h, (cost + (d - r) * D + c, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(20000)

times = int(input())
n, a, b, c, d = list(), list(), list(), list(), list()
for t in range(times):
    x = list(map(int, input().split()))
    n.append(x[0])
    a.append(x[1])
    b.append(x[2])
    c.append(x[3])
    d.append(x[4])


def f(N):
    if N == 0:
        return 0
    if N == 1:
        return D
    if N in dic:
        return dic[N]

    if N%2 == 0:
        N2 = f(N // 2) + A
    elif N%2 == 1:
        N2 = min(f((N-1) // 2) + D, f((N+1) // 2) + D) + A

    if N%3 == 0:
        N3 = f(N // 3) + B
    elif N%3 == 1:
        N3 = min(f((N-1) // 3) + D, f((N+2) // 3) + 2*D) + B
    elif N%3 == 2:
        N3 = min(f((N-2) // 3) + 2*D, f((N+1) // 3) + D) + B

    if N%5 == 0:
        N5 = f(N // 5) + C
    elif N%5 == 1:
        N5 = min(f((N-1) // 5) + D, f((N+4) // 5) + 4*D) + C
    elif N%5 == 2:
        N5 = min(f((N-2) // 5) + 2*D, f((N+3) // 5) + 3*D) + C
    elif N%5 == 3:
        N5 = min(f((N-3) // 5) + 3*D, f((N+2) // 5) + 2*D) + C
    elif N%5 == 4:
        N5 = min(f((N-4) // 5) + 4*D, f((N+1) // 5) + D) + C

    Y = min(N2, N3, N5, N*D)
    dic[N] = Y
    return Y


for t in range(times):
    N, A, B, C, D = n[t], a[t], b[t], c[t], d[t]
    dic = {}
    print(f(N))

Solution (Python):


def main():
    from heapq import heappush, heappop

    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())

        h = [(0, N)]  
        checked = set()

        ans = N * D + 1
        while h:
            cost, x = heappop(h)
            if cost >= ans: continue
            if x in checked: continue
            checked.add(x)

            
            if ans > cost + x * D:
                ans = cost + x * D

            for d, c in ((2, A), (3, B), (5, C)):
                
                
                
                nx, r = divmod(x, d)
                if nx not in checked:
                    heappush(h, (cost + r * D + c, nx))
                if (nx + 1) not in checked:
                    heappush(h, (cost + (d - r) * D + c, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
from functools import lru_cache

def solve(n,a,b,c,d):
    @lru_cache(None)
    def f(n):
        if n==0:
            return 0
        if n==1:
            return d
        ans=d*n
        q,r=divmod(n,2)
        if r==0:
            ans=min(ans,f(q)+a)
        else:
            ans=min(ans,f(q)+a+d,f(q+1)+a+d)
        q,r=divmod(n,3)
        if r==0:
            ans=min(ans,f(q)+b)
        elif r==1:
            ans=min(ans,f(q)+b+d)
        else:
            ans=min(ans,f(q+1)+b+d)
        q,r=divmod(n,5)
        if r==0:
            ans=min(ans,f(q)+c)
        elif r==1:
            ans=min(ans,f(q)+c+d)
        elif r==2:
            ans=min(ans,f(q)+c+d*2)
        elif r==3:
            ans=min(ans,f(q+1)+c+d*2)
        else:
            ans=min(ans,f(q+1)+c+d)
        return ans
    return f(n)

def main():
    t=int(input())
    for _ in range(t):
        n,a,b,c,d=map(int,input().split())
        print(solve(n,a,b,c,d))

if __name__=='__main__':
    main()

Solution (Python):


import sys
sys.setrecursionlimit(10**7)

t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {0: 0, 1: d}
    def cost(N):
        if N in memo:
            return memo[N]
        ans = N * d
        ks = [2, 3, 5]
        abc = [a, b, c]
        for i in range(3):
            k = ks[i]
            coin = abc[i]
            div, mod = divmod(N, k)
            pay = mod * d + coin

            
            
            
            ans = min(ans, pay + cost(div))
            if mod == 0:
                continue
            pay = (k - mod) * d + coin
            ans = min(ans, pay + cost(div + 1))
        memo[N] = ans
        return ans
    print(cost(n))

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque
import heapq

t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    hq = []
    memo = dict()
    memo[n] = 0
    heapq.heappush(hq, -n)
    while hq:
        val = -heapq.heappop(hq)
        for base, cost in zip([2, 3, 5], (a, b, c)):
            diff = val % base
            nval_p = val // base
            if nval_p in memo:
                
                memo[nval_p] = min(memo[nval_p], memo[val] + cost + d * diff)
                
                memo[nval_p] = min(memo[nval_p], memo[val] + (val - nval_p) * d)
            else:
                heapq.heappush(hq, -nval_p)
                
                memo[nval_p] = min(memo[val] + cost + d * diff, memo[val] + (val - nval_p) * d)
            if val % base != 0:
                nval_n = ((val - diff + base) // base)
                if nval_n in memo:
                    memo[nval_n] = min(memo[nval_n], memo[val] + cost + d * (base - diff))
                    
                    memo[nval_n] = min(memo[nval_n], memo[val] + (val - nval_n) * d)
                else:
                    heapq.heappush(hq, -nval_n)
                    memo[nval_n] = min(memo[val] + cost + d * (base - diff), memo[val] + (val - nval_n) * d)
    print(memo[0])

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10**7)

def solve(x,a,b,c,d):
    @lru_cache(None)
    def dfs(x):
        if x == 0:
            return 0
        if x == 1:
            return d
        l2 = x//2
        r2 = (x+1)//2
        l3 = x//3
        r3 = (x+2)//3
        l5 = x//5
        r5 = (x+4)//5
        count = x*d
        count = min(count,abs(l2*2-x)*d+a+dfs(l2))
        count = min(count,abs(r2*2-x)*d+a+dfs(r2))
        count = min(count,abs(l3*3-x)*d+b+dfs(l3))
        count = min(count,abs(r3*3-x)*d+b+dfs(r3))
        count = min(count,abs(l5*5-x)*d+c+dfs(l5))
        count = min(count,abs(r5*5-x)*d+c+dfs(r5))
        return count
    return dfs(x)
t = int(input())
for _ in range(t):
    n,a,b,c,d = map(int,input().split())
    print(solve(n,a,b,c,d))

Solution (Python):
from functools import lru_cache

T = int(input())

for t in range(T):
    N, A, B, C, D = map(int, input().split())

    @lru_cache(maxsize=None)
    def dist(n):
        if n == 0:
            return 0
        if n == 1:
            return D

        ret = min(
            D * n,
            D * abs(n - n // 5 * 5) + C + dist(n // 5),
            D * abs(n - (n + 4) // 5 * 5) + C + dist((n + 4) // 5),
            D * abs(n - n // 3 * 3) + B + dist(n // 3),
            D * abs(n - (n + 2) // 3 * 3) + B + dist((n + 2) // 3),
            D * abs(n - n // 2 * 2) + A + dist(n // 2),
            D * abs(n - (n + 1) // 2 * 2) + A + dist((n + 1) // 2),
        )

        return ret

    print(dist(N))

Solution (Python):


















def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)//2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(input())

nabcd = [list(map(int,input().split())) for _ in range(t)]


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print(func(n))

Solution (Python):


















def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)//2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(input())

nabcd = [list(map(int,input().split())) for _ in range(t)]


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print(func(n))

Solution (Python):

















def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)//2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(input())

nabcd = [list(map(int,input().split())) for _ in range(t)]


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print(func(n))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(x):
    if x == 0:
        return 0
    if x == 1:
        return d
    if x in dic:
        return dic[x]
    l2 = x//2
    r2 = (x+1)//2
    l3 = x//3
    r3 = (x+2)//3
    l5 = x//5
    r5 = (x+4)//5
    count = min(x*d,10**18)
    count = min(count,abs(l2*2-x)*d+a+dfs(l2))
    count = min(count,abs(r2*2-x)*d+a+dfs(r2))
    count = min(count,abs(l3*3-x)*d+b+dfs(l3))
    count = min(count,abs(r3*3-x)*d+b+dfs(r3))
    count = min(count,abs(l5*5-x)*d+c+dfs(l5))
    count = min(count,abs(r5*5-x)*d+c+dfs(r5))
    dic[x] = count
    return count

t = int(input())
for _ in range(t):
    n,a,b,c,d = map(int,input().split())
    dic = {}
    print(dfs(n))

Solution (Python):
T = int(input())
for i in range(T):
    n, A, B, C, D = map(int, input().split())
    memo = {}
 
    def herasu(N):
        if N == 0:
            return 0
        if N == 1:
            return D
        if N in memo:
            return memo[N]
        m = 100000000000000000000000
        if N % 2 == 0:
            m = min([m, A + herasu(N//2)])
        else:
            m = min([m, A + herasu(N//2) + D])
            m = min([m, A + herasu(N//2 + 1) + D])
        if N % 3 == 0:
            m = min(m, B + herasu(N//3))
        else:
            m = min([m, B + herasu(N//3) + (N%3) * D])
            m = min([m, B + herasu(N//3 + 1) + (3-(N%3)) * D])
        if N % 5 == 0:
            m = min(m, C + herasu(N // 5))
        else:
            m = min([m, C + herasu(N//5) + (N%5) * D])
            m = min([m, C + herasu(N//5 + 1) + (5-(N%5)) * D])
        m = min([m, D * N])
        memo[N] = m
        return m
 
    print(herasu(n))

Solution (Python):
import sys
from functools import lru_cache
def input(): return sys.stdin.readline().strip()


def main():

    """
    0から出発してNになるようにすると2^a 3^b 5^cをあらかじめ求めておかないといけなくて大変だったが
    Nから出発して0に向かうようにすれば数字がどんどん小さくなるから前計算不要なのか。。。

    そして\pm 1を掛け算のたびに挟むことになるから手詰まりになっていたけど、
    次の割り算をするのに、割り切れる数まで\pm 1してからさらに\pm 1をするのは確実に無駄とわかるから
    （\pm 1で移動→割り算）を１セットにして再帰してやれば確実に小さくなっていく！
    最後あたりに無限ループが起きる可能性があるから、そこは適切に処理すればよい。
    """

    T = int(input())
    for _ in range(T):
        N, a, b, c, d = map(int, input().split())

        @lru_cache(maxsize=None)
        def func(n):
            if n == 0: return 0
            if n == 1: return d
            val1 = func(n // 2) + a + d * (n % 2)
            val2 = func(n // 2 + 1) + a + d * (2 - (n % 2)) if n % 2 != 0 else float("inf")
            val3 = func(n // 3) + b + d * (n % 3)
            val4 = func(n // 3 + 1) + b + d * (3 - (n % 3)) if n % 3 != 0 else float("inf")
            val5 = func(n // 5) + c + d * (n % 5)
            val6 = func(n // 5 + 1) + c + d * (5 - (n % 5)) if n % 5 != 0 else float("inf")
            return min(val1, val2, val3, val4, val5, val6, d * n)
        
        print(func(N))


if __name__ == "__main__":
    main()

Solution (Python):
from functools import lru_cache

T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))


@lru_cache(maxsize=None)
def solve(n, A, B, C, D):
    if n == 0:
        return 0
    if n == 1:
        return D
    if n == 2:
        return min(D + D, A + D)

    ans = n * D

    for num, cost in zip([2, 3, 5], [A, B, C]):
        ans = min(
            solve((n + (num - n % num)) // num, A, B, C, D) + cost + D * (num - n % num),
            solve((n - n % num) // num, A, B, C, D) + cost + D * (n % num),
            ans,
        )

    return ans


for N, A, B, C, D in caseList:
    print(solve(N, A, B, C, D))

Solution (Python):
from functools import lru_cache
import sys

sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())

    @lru_cache(maxsize=None)
    def solve(n):
        if n == 1:
            return D

        res = n * D
        for v, c in zip([2, 3, 5], [A, B, C]):
            if n < v:
                continue
            q, m = divmod(n, v)
            if m == 0:
                res = min(solve(q) + c, res)
            else:
                res = min(res, min(solve(q) + c + D * m,
                                   solve(q + 1) + c + D * (v - m)))
        return res

    print(solve(N))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from functools import lru_cache

t = int(readline())
for _ in range(t):
    n, a, b, c, d = map(int, readline().split())

    @lru_cache(None)
    def check(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        res = n * d
        if n % 2 == 0:
            res = min(res, check(n // 2) + a)
        else:
            res = min(res, check(n // 2) + a + d, check(n // 2 + 1) + a + d)
        if n % 3 == 0:
            res = min(res, check(n // 3) + b)
        else:
            res = min(res, check(n // 3) + b + (n % 3) * d, check(n // 3 + 1) + b + (3 - n % 3) * d)
        if n % 5 == 0:
            res = min(res, check(n // 5) + c)
        else:
            res = min(res, check(n // 5) + c + (n % 5) * d, check(n // 5 + 1) + c + (5 - n % 5) * d)
        return res


    print(check(n))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
T=int(input())
def cost(n):
 if n in memo:
  return memo[n]
 else:
  ans=n*d
  if n//2 in memo:
   ans=min(memo[n//2]+a*min(1,memo[n//2])+(n%2)*d,ans)
  else:
   ans=min(cost(n//2)+a*min(1,cost(n//2))+(n%2)*d,ans)
  if n//3 in memo:
   ans=min(memo[n//3]+b*min(1,memo[n//3])+(n%3)*d,ans)
  else:
   ans=min(cost(n//3)+b*min(1,cost(n//3))+(n%3)*d,ans)
  if n//5 in memo:
   ans=min(memo[n//5]+c*min(1,memo[n//5])+(n%5)*d,ans)
  else:
   ans=min(cost(n//5)+c*min(1,cost(n//5))+(n%5)*d,ans)
  if n//2+1 in memo:
   ans=min(memo[n//2+1]+a+(2-(n%2))*d,ans)
  else:
   ans=min(cost(n//2+1)+a+(2-(n%2))*d,ans)
  if n//3+1 in memo:
   ans=min(memo[n//3+1]+b+(3-(n%3))*d,ans)
  else:
   ans=min(cost(n//3+1)+b+(3-(n%3))*d,ans)
  if n//5+1 in memo:
   ans=min(memo[n//5+1]+c+(5-(n%5))*d,ans)
  else:
   ans=min(cost(n//5+1)+c+(5-(n%5))*d,ans)
  memo[n]=ans
  return ans
for j in range(T):
 N,a,b,c,d = map(int,input().split())
 memo = {0:0,1:d,2:min(2*d,a+d)}
 print(cost(N))
 memo={}

Solution (Python):
def f(n):
 if (m:=s.get(n,-1))<0:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip((2,3,5),b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n));"*int(input()))

Solution (Python):
def f(n):
 if (m:=s.get(n,-1))<0:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());a=2,3,5;s={0:0,1:d};print(f(n));"*int(input()))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)    

def vc(value,cost,pt):
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return value,cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost
    
    if pt==1:
        v=value//2
        cost=cost+a+(value-v*2)*d
    elif pt==2:
        v=value//3
        cost=cost+b+(value-v*3)*d
    elif pt==3:
        v=value//5
        cost=cost+c+(value-v*5)*d
    elif pt==4:
        v=value//2+1
        cost=cost+a+(v*2-value)*d
    elif pt==5:
        v=value//3+1
        cost=cost+b+(v*3-value)*d
    elif pt==6:
        v=value//5+1
        cost=cost+c+(v*5-value)*d
    elif pt==7:
        v=0
        cost=cost+(value-v)*d
    return v,cost
    
def dfc(value,cost):
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost

    for i in range(7):
        value1,cost1=vc(value,cost,i+1)

        if value1 in vcs.keys():
            if vcs[value1]<=cost1:
                continue
            else:
                vcs[value1]=min(vcs[value1],cost1)     
                dfc(value1,cost1)
        else:
            vcs[value1]=cost1     
            dfc(value1,cost1)
        

t=int(input())

for i in range(t):
    n,a,b,c,d=map(int,input().split())





    
    vcs=dict()
    cost=dfc(n,0)
    print(vcs[0])

Solution (Python):
T = int(input())
K = []
for i in range(T):
    a = list(map(int,input().split()))
    K.append(a)

def pay(N):
    if N == 0:
        return 0
    if N == 1:
        return D
    if N in memo:
        return memo[N]

    m = float("inf")
    if N % 2 == 0:
        m = min(m, A + pay(N // 2))
    else:
        m = min(m, A + pay(N // 2) + D)
        m = min(m, A + pay(N // 2 + 1) + D)

    if N % 3 == 0:
        m = min(m, B + pay(N // 3))
    else:
        m = min(m, B + pay(N // 3) + D*(N%3))
        m = min(m, B + pay(N // 3 + 1) + D*(3 - N%3))

    if N % 5 == 0:
        m = min(m, C + pay(N // 5))
    else:
        m = min(m, C + pay(N // 5) + D*(N%5))
        m = min(m, C + pay(N // 5 + 1) + D*(5 - N%5))

    m = min(m, D*N)
    memo[N] = m
    return m

for i in range(T):
    memo = {}
    N, A, B, C, D = K[i]
    print(pay(N))

Solution (Python):
CACHE = None
A,B,C,D = None,None,None,None

def f(N):
    if N == 1:
        return D

    if N in CACHE:
        return CACHE[N]

    x = None
    if N%2 == 0:
        x = f(N//2) + A
    else:
        N2 = N//2
        x = min(f(N2+1), f(N2)) + A + D

    N3 = N%3
    if N3 == 0:
        x = min(x, f(N//3)+B)
    elif N3 == 1:
        x = min(x, f(N//3)+B+D)
    else:
        x = min(x, f(N//3+1)+B+D)
        
    if N >= 4:
        N5 = N%5
        if N5 == 0:
            x = min(x, f(N//5)+C)
        elif N5 <= 2:
            x = min(x, f(N//5)+C+D*N5)
        else:
            x = min(x, f(N//5+1)+C+D*(5-N5))

    if D <= x/N:
        x = min(x, D*N)
        
    CACHE[N] = x
    return x


T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int, input().split())
    CACHE = {}
    print(f(N))

Solution (Python):
T = int(input())
import sys
sys.setrecursionlimit(20000)

def f(n):
    if n == 0:
        return 0
    if n == 1:
        return D
    if n in dic:
        return dic[n]
    if n%2 == 0:
        n2 = f(n//2)+A
    else:
        n2 = min(f((n+1)//2), f((n-1)//2))+A+D
    if n%3 == 0:
        n3 = f(n//3)+B
    elif n%3 == 1:
        n3 = min(f((n-1)//3), f((n+2)//3)+D)+B+D
    else:
        n3 = min(f((n-2)//3)+D, f((n+1)//3))+B+D
    if n%5 == 0:
        n5 = f(n//5)+C
    elif n%5 == 1:
        n5 = min(f((n-1)//5)+D, f((n+4)//5)+4*D)+C
    elif n%5 == 2:
        n5 = min(f((n-2)//5)+2*D, f((n+3)//5)+3*D)+C
    elif n%5 == 3:
        n5 = min(f((n-3)//5)+3*D, f((n+2)//5)+2*D)+C
    else:
        n5 = min(f((n-4)//5)+4*D, f((n+1)//5)+D)+C
    res = min(n2, n3, n5, n*D)
    dic[n] = res
    return res
    
for _ in range(T):
    N,A,B,C,D = map(int, input().split())
    dic = {}
    print(f(N))

Solution (Python):
T = int(input())
K = []
for i in range(T):
    a = list(map(int,input().split()))
    K.append(a)

def pay(N):
    if N == 0:
        return 0
    if N == 1:
        return D
    if N in memo:
        return memo[N]

    m = float("inf")
    if N % 2 == 0:
        m = min(m, A + pay(N // 2))
    else:
        m = min(m, A + pay(N // 2) + D)
        m = min(m, A + pay(N // 2 + 1) + D)

    if N % 3 == 0:
        m = min(m, B + pay(N // 3))
    else:
        m = min(m, B + pay(N // 3) + D*(N%3))
        m = min(m, B + pay(N // 3 + 1) + D*(3 - N%3))

    if N % 5 == 0:
        m = min(m, C + pay(N // 5))
    else:
        m = min(m, C + pay(N // 5) + D*(N%5))
        m = min(m, C + pay(N // 5 + 1) + D*(5 - N%5))
        
    m = min(m, D*N)
    memo[N] = m
    return m

for i in range(T):
    memo = {}
    N, A, B, C, D = K[i]
    print(pay(N))

Solution (Python):
check=dict()
N,b,d=0,[],0


def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check[0]) if 0 in check else check[n]+n*d
    if n//ttf==0:
        check[n//ttf]=min(check[n]+(n%ttf)*d,check[n//ttf]) if n//ttf in check else check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**64

Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]

for N, A, B, C, D in Query:
    
    P = {}
    def solve(n):
        
        if n == 0:
            return INF
        if n in P:
            return P[n]
        if n == 1:
            return D
        S = n*D
        if n%2 == 0:
            S = min(S, solve(n//2)+A)
        else:
            S = min(S, solve(n//2)+A+D)
            S = min(S, solve((n+1)//2)+A+D)
        if n%3 == 0:
            S = min(S, solve(n//3)+B)
        else:
            S = min(S, solve(n//3)+B+D*(n%3))
            S = min(S, solve(n//3+1)+B+D*(3-n%3))
        if n%5 == 0:
            S = min(S, solve(n//5)+C)
        else:
            S = min(S, solve(n//5)+C+D*(n%5))
            S = min(S, solve(n//5+1)+C+D*(5-n%5))
        P[n] = S
        
        return S
    
    print(solve(N))

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def solve(N, A, B, C, D):

        
        @lru_cache(None)
        def f(N):
            
            if N == 0:
                return 0
            if N == 1:
                return D

            ret = D * N

            q, r = divmod(N, 2)
            
            if r == 0:
                ret = min(ret, f(q) + A)
            
            else:
                
                
                ret = min(ret, f(q) + A + D, f(q + 1) + A + D)

            q, r = divmod(N, 3)
            
            if r == 0:
                ret = min(ret, f(q) + B)
            
            elif r == 1:
                ret = min(ret, f(q) + B + D)
            
            else:
                ret = min(ret, f(q + 1) + B + D)

            q, r = divmod(N, 5)
            
            if r == 0:
                ret = min(ret, f(q) + C)
            
            elif r == 1:
                ret = min(ret, f(q) + C + D)
            
            elif r == 2:
                ret = min(ret, f(q) + C + D + D)
            
            elif r == 3:
                ret = min(ret, f(q + 1) + C + D + D)
            
            else:
                ret = min(ret, f(q + 1) + C + D)

            return ret

        return f(N)

    t = int(input())
    for _ in range(t):
        n, a, b, c, d = map(int, input().split())
        print(solve(n, a, b, c, d))


if __name__ == '__main__':
    resolve()

Solution (Python):
def f(n):
 if(m:=s.get(n))is None:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());a=2,3,5;s={0:0,1:d};print(f(n));"*int(input()))

Solution (Python):
a=2,3,5
def f(n):
 if(m:=s.get(n))is None:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n));"*int(input()))

Solution (Python):
a=2,3,5
def f(n):
 if(m:=s.get(n))is None:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
for _ in[0]*int(input()):n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n))

Solution (Python):
a=2,3,5
def f(n):
 if(m:=s.get(n))is None:s[n]=(m:=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)]))
 return m
for _ in[0]*int(input()):n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n))

Solution (Python):
a=2,3,5
def f(n):
 m=s.get(n)
 if m is None:s[n]=(m:=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)]))
 return m
for _ in[0]*int(input()):n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n))

Solution (Python):

from sys import setrecursionlimit
setrecursionlimit(10**8)
INF = float("inf")


def main():

    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())
        memo = {0: 0, 1: D}

        def f(n):
            memo[n] = n*D
            ans = memo[n]
            for cost, p in zip((A, B, C), (2, 3, 5)):
                d, m = divmod(n, p)
                if d not in memo:
                    f(d)
                if d+1 not in memo:
                    f(d+1)
                ans = min(ans, memo[d] + cost + m*D)
                ans = min(ans, memo[d+1] + cost + (p-m)*D)
            memo[n] = ans
            return ans
        print(f(N))

    return


if __name__ == '__main__':
    main()