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):
divs = [2, 3, 5]

t = int(input())

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]

    dp = {0: 0}

    def dfs(x):
        if x in dp:
            return dp[x]

        ret = x * d

        for cost, div in zip(costs, divs):
            lx = x // div * div
            ret = min(ret, dfs(lx // div) + cost + (x - lx) * d)

            if lx == x:
                continue
            lx += div
            if lx // div >= x:
                continue
            ret = min(ret, dfs(lx // div) + cost + (lx - x) * d)

        dp[x] = ret
        return ret

    print(dfs(n))

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

Solution (Python):
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      m = min(m, *(f(k) + abs(p * k - n) * d + c for k in (n // p, -(-n // p))))
    memo[n] = m
  return m

t = int(input())
for _ in range(t):
  n, *b, d = map(int, input().split())
  memo = {0: 0, 1: d}
  print(f(n))

Solution (Python):
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      m = min(m, *(f(k) + abs(p * k - n) * d + c for k in {n // p, -(-n // p)}))
    memo[n] = m
  return m

t = int(input())
for _ in range(t):
  n, *b, d = map(int, input().split())
  memo = {0: 0, 1: d}
  print(f(n))

Solution (Python):
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      k, r = divmod(n, p);
      m = min(m, f(k) + r * d + c, r  and f(k + 1) + (p - r) * d + c or m)
    memo[n] = m
  return m

t = int(input())
for _ in range(t):
  n, *b, d = map(int, input().split())
  memo = {0: 0, 1: d}
  print(f(n))

Solution (Python):
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    s = {(0, 0, 0)}.union(*({(n // p, p, c), (-(-n // p), p, c)} for p, c in zip(a, b)))
    m = min(f(x) + abs(x * p - n) * d + c for x, p, c in s)
    memo[n] = m
  return m

t = int(input())
for _ in range(t):
  n, *b, d = map(int, input().split())
  memo = {0: 0, 1: d}
  print(f(n))

Solution (Python):
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      k, r = divmod(n, p);
      m = min(m, f(k) + r * d + c)
      if r:
       m = min(m, f(k + 1) + (p - r) * d + c)
    memo[n] = m
  return m

t = int(input())
for _ in range(t):
  n, *b, d = map(int, input().split())
  memo = {0: 0, 1: d}
  print(f(n))

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

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

    used = {}

    def solve(t):
        if t in used:
            return used[t]
        if t <= 1:
            return t * d

        res = d * t
        for x, y in zip([2, 3, 5], [a, b, c]):
            if t % x == 0:
                res = min(res, solve(t // x) + y)
            else:
                res = min(res, solve(t // x) + y + (t - t // x * x) * d)
                res = min(res, solve(t // x + 1) + y + ((t // x + 1) * x - t) * d)

        used[t] = res
        return res

    print(solve(n))

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

Solution (Python):
from functools import lru_cache
for _ in range(int(input())):
    n,a,b,c,d=map(int,input().split())
    @lru_cache(None)
    def f(k):
        if k==0:return 0
        if k==1:return d
        return min(k*d,f(k//5)+c+k%5*d,f(k//3)+b+k%3*d,f(k//2)+a+k%2*d,f((k+4)//5)+c+-k%5*d,f((k+2)//3)+b+-k%3*d,f((k+1)//2)+a+-k%2*d)
    print(f(n))

Solution (Python):
import sys
sys.setrecursionlimit(int(1e6))
 
def solve():
    num = {}
    def saiki(N):
        
        res = N*D
        if N == 0:
            return 0
        elif N == 1:
            return D
        if N in num:
            return num[N]
        
        if N%2 == 0:
            res = min(res,saiki(N//2)+A)
        else:
            res = min(res,saiki((N+1)//2)+A+D,saiki((N-1)//2)+A+D)
        
        if N%3 == 0:
            res = min(res,saiki(N//3)+B)
        else:
            res = min(res,saiki(N//3)+D*(N%3)+B,saiki(N//3+1)+D*(3-N%3)+B)
        
        if N%5 == 0:
            res = min(res,saiki(N//5)+C)
        else:
            res = min(res,saiki(N//5)+D*(N%5)+C,saiki(N//5+1)+D*(5-N%5)+C)
        
        
        num[N] = res
 
        return res
    
    print(saiki(N))
 
for _ in range(int(input())):
    N,A,B,C,D = map(int,input().split())
    solve()

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

Solution (Python):
from functools import lru_cache


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

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

        cost = n * D
        for div, c in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(n, div)

            if r == 0:
                cost = min(cost, dfs(q) + c)
            else:
                cost = min(cost, dfs(q) + c + D * r)
                cost = min(cost, dfs(q+1) + c + D * (div - r))
        return cost

    return dfs(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):
def f(k):
    if k==1:return d
    if k==0:return 0
    if k in m:return m[k]
    s=k*d
    s=min(s,f(k//2)+a+k%2*d,f((k+1)//2)+a+-k%2*d,f(k//3)+b+k%3*d,f((k+2)//3)+b+-k%3*d,f(k//5)+c+k%5*d,f((k+4)//5)+c+-k%5*d)
    m[k]=s
    return s
for _ in range(int(input())):
    m={}
    n,a,b,c,d=map(int,input().split())
    print(f(n))

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
t=int(input())
INF=10**19
def dfs(k):
    if k==1:return d
    if k==0:return 0
    if k in dic:return dic[k]
    ans=k*d
    ans=min(ans,dfs(k//2)+a+k%2*d,dfs((k+1)//2)+a+-k%2*d,dfs(k//3)+b+k%3*d,dfs((k+2)//3)+b+-k%3*d,dfs(k//5)+c+k%5*d,dfs((k+4)//5)+c+-k%5*d)
    dic[k]=ans
    return ans
for _ in range(t):
    dic={}
    n,a,b,c,d=map(int,input().split())
    print(dfs(n))

Solution (Python):
T = int(input())

from heapq import *

for ti in range(1, T + 1):
    n, a, b, c, d = tuple(map(int, input().split()))
    pq = []
    heappush(pq, (0, n))  
    visited = set()  
    while True:
        top = heappop(pq)
        cost, posi = top
        cost, posi = cost, posi
        if posi in visited:
            continue
        else:
            visited.add(posi)
        if posi == 0:
            print(cost)
            break
        costnaive = cost + d * posi
        heappush(pq, (costnaive, 0))
        for mode, margin in [(2, a), (3, b), (5, c)]:
            modulo = posi % mode
            costdown = cost + margin + modulo * d
            downto = (posi - modulo) // mode
            costup = cost + margin + (mode - modulo) * d
            upto = (posi + (mode - modulo)) // mode
            heappush(pq, (costdown, downto))
            heappush(pq, (costup, upto))

Solution (Python):

from functools import lru_cache

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



def slv(N, A, B, C, D):
    @lru_cache(maxsize=None)
    def f(n):
        if n == 1:
            return D
        if n == 0:
            return 0
        ans = n*D

        i = (n // 2) * 2
        ans = min(ans, f(i//2) + A + D*abs(n-i))
        i = -(-n // 2) * 2
        ans = min(ans, f(i//2) + A + D*abs(n-i))

        i = (n // 3) * 3
        ans = min(ans, f(i//3) + B + D*abs(n-i))
        i = -(-n // 3) * 3
        ans = min(ans, f(i//3) + B + D*abs(n-i))

        i = (n // 5) * 5
        ans = min(ans, f(i//5) + C + D*abs(n-i))
        i = -(-n // 5) * 5
        ans = min(ans, f(i//5) + C + D*abs(n-i))
        return ans

    return f(N)


def main():
    T = read_int()
    for _ in range(T):
        N, A, B, C ,D = read_int_n()
        print(slv(N, A, B, C, D))


if __name__ == '__main__':
    main()

Solution (Python):
T = int(input())

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

    def dist(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo:
            return memo[n]
        
        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)
        )

        memo[n] = ret
        return ret
    print(dist(N))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict

t = int(input())

for _ in range(t):
    n,a,b,c,d = map(int,input().split())
    dic = defaultdict(int)
    dic[0] = 0
    dic[1] = d

    def calc(x):
        if(x==0):
            return 0
        if(dic[x] != 0):
            return dic[x]

        tmp = x*d
        if(x%2==0):
            tmp = min(tmp, calc(x//2) + a)
        else:
            tmp = min(tmp, calc(x//2) + a + d, calc(x//2 + 1) + a + d)
        if(x%3==0):
            tmp = min(tmp, calc(x//3) + b)
        elif(x%3==1):
            tmp = min(tmp, calc(x//3) + b + d)
        else:
            tmp = min(tmp, calc(1 + x//3) + b + d)
        if(x%5==0):
            tmp = min(tmp, calc(x//5) + c)
        elif(x%5 < 3):
            tmp = min(tmp, calc(x//5) + c + d*(x%5))
        else:
            tmp = min(tmp, calc(1 + x//5) + c + d*(5 - x%5))

        dic[x] = tmp
        return tmp

    print(calc(n))

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


def main():
    for _ in [0]*int(input()):
        N, A, B, C, D = map(int, input().split())
        S = {}

        def dfs(n):
            if n == 0:
                return 0
            if n == 1:
                return D
            if n in S:
                return S[n]

            cost = n*D
            r = n % 2
            if r == 0:
                cost = min(cost, dfs(n//2)+A)
            else:
                cost = min(cost, dfs(n//2)+A+D)
                cost = min(cost, dfs(n//2+1)+A+D)
            r = n % 3
            if r == 0:
                cost = min(cost, dfs(n//3)+B)
            else:
                cost = min(cost, dfs(n//3)+B+D*r, dfs(n//3+1)+B+D*(3-r))
            r = n % 5
            if r == 0:
                cost = min(cost, dfs(n//5)+C)
            else:
                cost = min(cost, dfs(n//5)+C+D*r, dfs(n//5+1)+C+D*(5-r))

            S[n] = cost
            return cost

        print(dfs(N))


if __name__ == '__main__':
    main()

Solution (Python):
def main():

    T = int(input())

    def dfs(i, A, B, C, D):
        if i not in memo:
            v = i * D
            if i % 2 == 0:
                v = min(v, A + dfs(i//2, A, B, C, D))
            else:
                v = min(v, D + A + dfs((i-1)//2, A, B, C, D))
                v = min(v, D + A + dfs((i+1)//2, A, B, C, D))
            if i % 3 == 0:
                v = min(v, B + dfs(i//3, A, B, C, D))
            else:
                v = min(v, D*(i%3) + B + dfs((i-i%3)//3, A, B, C, D))
                v = min(v, D*(3-i%3) + B + dfs((i+3-i%3)//3, A, B, C, D))
            if i % 5 == 0:
                v = min(v, C + dfs(i//5, A, B, C, D))
            else:
                v = min(v, D*(i%5) + C + dfs((i-i%5)//5, A, B, C, D))
                v = min(v, D*(5-i%5) + C + dfs((i+5-i%5)//5, A, B, C, D))
            memo[i] = v
        return memo[i]

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

        print(dfs(N, A, B, C, D))

if __name__ == '__main__':
    main()

Solution (Python):

from functools import lru_cache

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



def slv(N, A, B, C, D):
    @lru_cache(maxsize=None)
    def f(n):
        ans = n*D
        for i in range(-min(2, n), min(3, n)):
            m = n + i
            i = abs(i)
            if m == 0:
                continue

            if m % 5 == 0:
                ans = min(ans, f(m//5) + C + D*i)
            if m % 3 == 0:
                ans = min(ans, f(m//3) + B + D*i)
            if m % 2 == 0:
                ans = min(ans, f(m//2) + A + D*i)
        return ans

    return f(N)


def main():
    T = read_int()
    for _ in range(T):
        N, A, B, C ,D = read_int_n()
        print(slv(N, A, B, C, D))


if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())
import heapq
def tr(pnt,m):
  try:
    if use[m] > pnt:
      heapq.heappush(now,[pnt,m])
      use[m] = pnt
  except:
    heapq.heappush(now,[pnt,m])
    use[m] = pnt
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n]]
  use = {}
  ans = n*d
  while True:
    sc,num = heapq.heappop(now)
    ans = min(ans,sc+num*d)
    if num == 1:
      print(ans)
      break

    if num % 2 == 0:
      tr(sc+a,num//2)
    else:
      tr(sc+a+d,(num-1)//2)
      tr(sc+a+d,(num+1)//2)
    
    if num % 3 == 0:
      tr(sc+b,num//3)
    elif num % 3 == 1:
      tr(sc+b+d,(num-1)//3)
    else:
      tr(sc+b+d,(num+1)//3)
    
    if num % 5 == 0:
      tr(sc+c,num//5)
    elif num % 5 == 1:
      tr(sc+c+d,(num-1)//5)
    elif num % 5 == 2:
      tr(sc+c+2*d,(num-2)//5)
    elif num % 5 == 3:
      tr(sc+c+2*d,(num+2)//5)
    else:
      tr(sc+c+d,(num+1)//5)

Solution (Python):
T=int(input())
from functools import lru_cache

for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    @lru_cache(maxsize=None)  
    def solve(N):
        if N==0:
            return 0
        if N==1:
            return D
        tmp=N*D    
        if N%2==0:
            tmp=min(tmp,solve(N//2)+A)
        else:
            tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
        if N%3==0:
            tmp=min(tmp,solve(N//3)+B)
        else:
            b=N%3 
            tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
        if N%5==0:
            tmp=min(tmp,solve(N//5)+C)
        else:
            c=N%5
            tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
        return tmp

    print(solve(N))

Solution (Python):



t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {0: 0, 1: d}

    def dfs(m):
        if m in memo:
            return memo[m]
        else:
            res1 = m * d

            res2 = (m % 2) * d + a + dfs(m // 2)
            res3 = (m % 3) * d + b + dfs(m // 3)
            res4 = (m % 5) * d + c + dfs(m // 5)

            res5 = ((2 - (m % 2)) % 2) * d + a + dfs(
                (m + (2 - (m % 2)) % 2) // 2)
            res6 = ((3 - (m % 3)) % 3) * d + b + dfs(
                (m + (3 - (m % 3)) % 3) // 3)
            res7 = ((5 - (m % 5)) % 5) * d + c + dfs(
                (m + (5 - (m % 5)) % 5) // 5)

            memo[m] = min(res1, res2, res3, res4, res5, res6, res7)
            return memo[m]

    ans = dfs(n)
    print(ans)

Solution (Python):
t = int(input())
import heapq
def tr(pnt,m):
  try:
    if use[m] > pnt:
      heapq.heappush(now,[pnt,m])
      use[m] = pnt
  except:
    heapq.heappush(now,[pnt,m])
    use[m] = pnt
inf = 10**18
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n]]
  use = {}
  mini = 10**18
  ans = n * d
  while True:
    sc,num = heapq.heappop(now)
    ans = min(ans,sc+d*num)
    if num == 1:
      print(ans)
      break
    if num % 2 == 0:
      tr(sc+a,num//2)
    else:
      tr(sc+a+d,(num-1)//2)
      tr(sc+a+d,(num+1)//2)
    
    if num % 3 == 0:
      tr(sc+b,num//3)
    elif num % 3 == 1:
      tr(sc+b+d,(num-1)//3)
    else:
      tr(sc+b+d,(num+1)//3)
    
    if num % 5 == 0:
      tr(sc+c,num//5)
    elif num % 5 == 1:
      tr(sc+c+d,(num-1)//5)
    elif num % 5 == 2:
      tr(sc+c+2*d,(num-2)//5)
    elif num % 5 == 3:
      tr(sc+c+2*d,(num+2)//5)
    else:
      tr(sc+c+d,(num+1)//5)

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)


memo = {}

def solve():
    N,A,B,C,D = map(int,input().split())
    global memo
    memo = {0:0,1:D}
    return process(N,N,A,B,C,D)


def process(M,N,A,B,C,D):
    
    
    global memo
    if M in memo:
        return memo[M]
    res = process((M-M%2)//2,N,A,B,C,D) + A + (M%2) * D
    res = min(res,process((M+M%2)//2,N,A,B,C,D) + A + (M%2) * D)
    res = min(res,process((M-M%3)//3,N,A,B,C,D) + B + (M%3) * D)
    res = min(res,process((M+3-M%3)//3,N,A,B,C,D) + B + (3-M%3) * D)
    res = min(res,process((M-M%5)//5,N,A,B,C,D) + C + (M%5) * D)
    res = min(res,process((M+5-M%5)//5,N,A,B,C,D) + C + (5-M%5) * D)
    res = min(res,M*D)
    memo[M] = res
    return res


def main():
    T = int(input())

    for i in range(T):
        res = solve()
        print(res)



main()

Solution (Python):
import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])

Solution (Python):
import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])

Solution (Python):
from collections import deque

t = int(input())
cases = [tuple(int(v) for v in input().split()) for _ in range(t)]


def get_simple_price(n, p, d, m):
    price = 0
    while n != 0:
        mod = n % m
        if mod != 0:
            price += mod * d
            n -= mod
        if n != 0:
            price += p
            n //= m
    return price


def discover(n, a, b, c, d):
    
    limit = min(
        get_simple_price(n, a, d, 2),
        get_simple_price(n, b, d, 3),
        get_simple_price(n, c, d, 5),
        n * d,
    )
    memo = {}

    queue = deque([(n, 0)])
    while len(queue) > 0:
        t, p = queue.pop()
        if t == 0:
            if p < limit:
                limit = p
            continue
        if t == 1:
            queue.append((0, p + d))
            continue
        if t in memo:
            if p < memo[t]:
                memo[t] = p
            else:
                continue
        else:
            memo[t] = p

        queue.append((0, p + t * d))
        mod = t % 2
        queue.append((t // 2, p + a + d * mod))
        if mod != 0:
            queue.append((t // 2 + 1, p + a + d * (2 - mod)))
        mod = t % 3
        queue.append((t // 3, p + b + d * mod))
        if mod != 0:
            queue.append((t // 3 + 1, p + b + d * (3 - mod)))
        mod = t % 5
        queue.append((t // 5, p + c + d * mod))
        if mod != 0:
            queue.append((t // 5 + 1, p + c + d * (5 - mod)))

    return limit


for n, a, b, c, d in cases:
    print(discover(n, a, b, c, d))

Solution (Python):
t=int(input())

def rec(x,memo,a,b,c,d):
    if x in memo:
        return memo[x]
    
    ans=x*d
    ans=min(ans,rec(x//2,memo,a,b,c,d)+a+(x%2)*d)
    ans=min(ans,rec((x+1)//2,memo,a,b,c,d)+a+((x+1)//2*2-x)*d)
    ans=min(ans,rec(x//3,memo,a,b,c,d)+b+(x%3)*d)
    ans=min(ans,rec((x+2)//3,memo,a,b,c,d)+b+((x+2)//3*3-x)*d)
    ans=min(ans,rec(x//5,memo,a,b,c,d)+c+(x%5)*d)
    ans=min(ans,rec((x+4)//5,memo,a,b,c,d)+c+((x+4)//5*5-x)*d)

    memo[x]=ans
    return ans

for _ in range(t):
    n,a,b,c,d=list(map(int,input().split()))
    memo={0:0,1:d}
    print(rec(n,memo,a,b,c,d))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
T=int(input())

def dfs(n):
  if n in dic:
    return dic[n]  
  
  m2=n%2
  if m2==0:
    score_a1=A+dfs(n//2)
    score_a2=A+dfs(n//2)
  else:
    score_a1=m2*D+A+dfs((n-m2)//2)
    score_a2=m2*D+A+dfs((n+(2-m2))//2)

  m3=n%3
  if m3==0:
    score_b1=B+dfs(n//3)
    score_b2=B+dfs(n//3)
  else:
    score_b1=m3*D+B+dfs((n-m3)//3)
    score_b2=(3-m3)*D+B+dfs((n+(3-m3))//3)

  m5=n%5
  if m5==0:
    score_c1=C+dfs(n//5)
    score_c2=C+dfs(n//5)
  else:
    score_c1=m5*D+C+dfs((n-m5)//5)
    score_c2=(5-m5)*D+C+dfs((n+(5-m5))//5)

  score_d=n*D
  ret=min(score_a1,score_a2,score_b1,score_b2,score_c1,score_c2,score_d)
  dic[n]=ret
  return ret

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

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

def calc(nn, a,b,c,d):
    global dp

    if nn in dp :
        return dp[nn]
    if nn == 0:
        return 0
    
    ncost = []
    
    if nn%2 == 0:
        tcost = calc(nn//2, a,b,c,d)
        ncost.append(tcost + min((nn//2)*d , a))
    else:
        tcost = calc((nn-1)//2, a,b,c,d)
        ncost.append(tcost + min(((nn-1)//2)*d + d , a+d))

        tcost = calc((nn+1)//2, a,b,c,d)
        ncost.append(tcost + min(((nn+1)//2)*d + d , a+d))

    
    if nn%3 == 0:
        tcost = calc(nn//3, a,b,c,d)
        ncost.append(tcost + min((nn//3)*2*d , b))
    else:
        m = nn%3
        tcost = calc((nn-m)//3,  a,b,c,d)
        ncost.append(tcost + min(((nn-m)//3)*2*d + d*m , b+d*m) )
        tcost = calc((nn+(3-m))//3, a,b,c,d)
        ncost.append(tcost + min((nn+(3-m))//3*2*d + d*(3-m) , b+d*(3-m)))

    
    if nn%5 == 0:
        tcost = calc(nn//5, a,b,c,d)
        ncost.append(tcost + min((nn//5)*4*d , c))
    else:
        m = nn%5
        tcost = calc((nn-m)//5 , a,b,c,d)
        ncost.append(tcost +  min(((nn-m)//5)*4*d + d*m , c+d*m))
        tcost = calc((nn+(5-m))//5, a,b,c,d)
        ncost.append(tcost +  min((nn+(5-m))//5*4*d + d*(5-m) , c+d*(5-m)))

    mincost = min(ncost) 
    dp[nn] = mincost
    return mincost

t = ii()
ans = []
for i in range(t):
    n,a,b,c,d = mi()
    dp = {}
    dp[1] = d
    ansi = calc(n,a,b,c,d)
    ans.append(ansi)

for i in range(t):
    print(ans[i])

Solution (Python):
from collections import defaultdict
dic_h = defaultdict(int)
dic_h[0] = 9999999999
dic_h[1] = 8

t = int(input())

cnt = 0
def tk(v,a,b,c,d):
    global cnt,dic_h
    if dic_h[v] != 0 :
        return dic_h[v]
    
    pas1 = v // 2
    if v == 2 :
        pas2 = 0  
    else:
        pas2 = pas1 + 1 
    pam1 =  v % 2 
    pam2 = 2 - pam1
    pbs1 = v // 3
    pbs2 = pbs1 + 1
    pbm1 = v % 3 
    pbm2 = 3 -pbm1  
    pcs1 = v // 5
    pcs2 = pcs1 +  1
    pcm1 = v % 5 
    pcm2 = 5 - pcm1

    koho_a1 = tk(pas1,a,b,c,d) + pam1*d + a
    koho_b1 = tk(pbs1,a,b,c,d) + pbm1*d + b
    koho_c1 = tk(pcs1,a,b,c,d) + pcm1*d + c
    koho_a2 = tk(pas2,a,b,c,d) + pam2*d + a
    koho_b2 = tk(pbs2,a,b,c,d) + pbm2*d + b
    koho_c2 = tk(pcs2,a,b,c,d) + pcm2*d + c
    
    ret = min(v*d,koho_a1,koho_a2,koho_b1,koho_b2,koho_c1,koho_c2 ) 
    dic_h[v] = ret
    
    return ret

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    
    dic_h = defaultdict(int)
    dic_h[0] = 9999999999    
    dic_h[1] = d
    print(tk(n,a,b,c,d))

Solution (Python):
T = int(input())

testcase = [list(map(int,input().split())) for i in range(T)]

from functools import lru_cache

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

for n,a,b,c,d in testcase:
    print(f(n,a,b,c,d))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

    
        
t = int(input())
for i in range(t):
    ans = {}
    def sub(n,A,B,C,D):
        if n==1:
            ans[1] = D
            return D
        if n==0:
            return 0
        if n in ans:
            return ans[n]
        v = n * D
        if n%2==0:
            v = min(v, sub(n//2, A, B, C, D)+A)
        else:
            v = min(v, sub(n//2, A, B, C, D)+A+D)
            if n>2:
                v = min(v, sub(n//2+1, A, B, C, D)+A+D)
        if n%3==0:
            v = min(v, sub(n//3, A, B, C, D)+B)
        else:
            if n>=3:
                v = min(v, sub(n//3, A, B, C, D)+B+(n%3)*D)
                v = min(v, sub(n//3+1, A, B, C, D)+B+(3-(n%3))*D)
        if n%5==0:
            v = min(v, sub(n//5, A, B, C, D)+C)
        else:
            if n>=5:
                v = min(v, sub(n//5, A, B, C, D)+C+(n%5)*D)
                v = min(v, sub(n//5+1, A, B, C, D)+C+(5-(n%5))*D)
        ans[n] = v
        return v

    n, A,B,C,D = map(int, input().split())
    print(sub(n,A,B,C,D))