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):
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0

def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=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 check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

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

Solution (Python):

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


T = ir()

@lru_cache(None)
def F(x, A, B, C, D):
    if x == 1:
        return D
    elif x <= 0:
        return INF
    if x&1:
        a = min(F(x//2, A, B, C, D) + D + A, F((x+1)//2, A, B, C, D) + D + A)
    else:
        a = F(x//2, A, B, C, D) + A
    cnt2 = 0
    y = x
    while y%3 != 0:
        y -= 1
        cnt2 += 1
    b = F(y//3, A, B, C, D) + B + cnt2 * D
    if (x+1)%3 == 0:
        t = F((x+1)//3, A, B, C, D) + B + D
        b = min(b, t)
    cnt3 = 0
    y = x
    while y%5 != 0:
        y -= 1
        cnt3 += 1
    c = min(F(y//5, A, B, C, D) + C + cnt3 * D, F((y+5)//5, A, B, C, D) + C + (5-cnt3) * D)
    d = x * D
    ret = min(a, b, c, d)
    return ret

INF = float('inf')
for _ in range(T):
    N, A, B, C, D = lr()
    answer = F(N, A, B, C, D)
    print(answer)

Solution (Python):
a = 2, 3, 5
 
def f(n):
  m = memo.get(n)
  if m is None:
    m = min([d * n] + [f(k) + abs(p * k - n) * d + c for p, c in zip(a, b) for k in (n // p, 0--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):

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


T = ir()

@lru_cache(None)
def F(x, A, B, C, D):
    if x == 1:
        return D
    elif x <= 0:
        return INF
    if x&1:
        a = min(F(x//2, A, B, C, D) + D + A, F((x+1)//2, A, B, C, D) + D + A)
    else:
        a = F(x//2, A, B, C, D) + A
    cnt2 = 0
    y = x
    while y%3 != 0:
        y -= 1
        cnt2 += 1
    b = F(y//3, A, B, C, D) + B + cnt2 * D
    if (x+1)%3 == 0:
        t = F((x+1)//3, A, B, C, D) + B + D
        b = min(b, t)
    cnt3 = 0
    y = x
    while y%5 != 0:
        y -= 1
        cnt3 += 1
    c = min(F(y//5, A, B, C, D) + C + cnt3 * D, F((y+5)//5, A, B, C, D) + C + (5-cnt3) * D)
    ret = min(a, b, c)
    if x < 10 ** 12 or D < 10 ** 9:
        d = x * D
        ret = min(ret, d)
    return ret

INF = float('inf')
for _ in range(T):
    N, A, B, C, D = lr()
    answer = F(N, A, B, C, D)
    print(answer)

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

T = int(input())
INF = 10**18

for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    DC = tuple(zip((2, 3, 5), (A, B, C)))

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = now * D
        for div, cost in DC:
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
            )
        return ret

    print(search(N))

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq

INF = float("inf")











t = int(input())
for _ in range(t):
    n, a, b, c, da = map(int, input().split())
    hq = [(0, n)]
    d = defaultdict(lambda: 10 ** 25)
    d[n] = 0
    while hq:
        cs, p = heapq.heappop(hq)
        if d[p] < cs:
            continue
        if d[p // 2] > cs + a + (p % 2) * da:
            heapq.heappush(hq, (cs + a + (p % 2) * da, p // 2))
            d[p // 2] = cs + a + (p % 2) * da
        if d[p // 2 + 1] > cs + a + da:
            heapq.heappush(hq, (cs + a + da, p // 2 + 1))
            d[p // 2 + 1] = cs + a + da
        if d[p // 3] > cs + b + (p % 3) * da:
            heapq.heappush(hq, (cs + b + (p % 3) * da, p // 3))
            d[p // 3] = cs + b + (p %3) * da
        if d[p // 3 + 1] > cs + b +  (1+(p%3)%2)* da:
            heapq.heappush(hq, (cs + b + (1+(p%3)%2) * da, p // 3 + 1))
            d[p // 3 + 1] = cs + b + (1+(p%3)%2) * da
        ccc = p % 5
        if ccc <= 2:
            if d[p//5] > cs+c+ccc*da:
                heapq.heappush(hq,(cs+c+ccc*da,p//5))
                d[p//5] = cs+c+ccc*da
            if d[p//5 +1] > cs+c+(ccc+1)*da:
                heapq.heappush(hq,(cs+c+(ccc+1)*da,p//5 +1))
                d[p//5 +1] = cs+c+(ccc+1)*da
        else:
            if d[p//5] > cs+c+(6-ccc)*da:
                heapq.heappush(hq,(cs+c+(6-ccc)*da,p//5))
                d[p//5] = cs+c+(6-ccc)*da
            if d[p//5 +1] > cs+c+(5-ccc)*da:
                heapq.heappush(hq,(cs+c+(5-ccc)*da,p//5 +1))
                d[p//5 +1] = cs+c+(5-ccc)*da
    ans = 10 ** 25
    for k, v in d.items():
        ans = min(ans, k * da + v)
    print(ans)

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

T = int(input())
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = now * D
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
            )
        return ret

    print(search(N))

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

T = int(input())
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = INF
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
                now * D
            )
        return ret

    print(search(N))

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

T = int(input())
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = INF
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
                now * D
            )
        return ret

    print(search(N))

Solution (Python):

t = int(input())
import heapq
def tr(score,number):
  try:
    if use[number] > score:
      use[number] = score
      heapq.heappush(now,[score,number])
  except:
    use[number] = score
    heapq.heappush(now,[score,number])
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n]]
  ans = n * d
  use = {n:0}
  while True:
    sc,num = heapq.heappop(now)
    ans = min(ans,sc+num*d)
    if use[num] < sc:
      continue
    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())
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,queue,math,copy,itertools,bisect,collections
from heapq import *


def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    for _ in range(NI()):
        N,A,B,C,D = LI()

        q = []
        heapify(q)

        memo = {}

        def push(c,n):
            if memo.get(n,INF) > c :
                heappush(q,(c,n))
                memo[n] = c


        push(0,N)

        while q:
            c,n = heappop(q)
            m = [0] * 9
            if n == 1:
                print(c+D)
                break

            if n % 2 == 0:
                push(c+min(A,n//2*D),n//2)
            else:
                m[1] = m[-1] = 1
            if n % 3 == 0:
                push(c+min(B,n//3*2*D),n//3)
            else:
                m[3-(n%3)] = m[-(n%3)] = 1
            if n % 5 == 0:
                push(c+min(C,n//5*4*D),n//5)
            else:
                m[5-(n%5)] = m[-(n%5)] = 1
            for i in range(-4,5):
                if m[i] and n+i > 0: push(c+D*abs(i),n+i)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
from collections import defaultdict, deque
t = int(input())
for _ in range(t):
    n, a, b, c, da = map(int, input().split())
    hq = [(0, n)]
    d = defaultdict(lambda: 10 ** 25)
    d[n] = 0
    while hq:
        cs, p = heapq.heappop(hq)
        if d[p] < cs:
            continue
        if d[p // 2] > cs + a + (p % 2) * da:
            heapq.heappush(hq, (cs + a + (p % 2) * da, p // 2))
            d[p // 2] = cs + a + (p % 2) * da
        if d[p // 2 + 1] > cs + a + (2 - p % 2):
            heapq.heappush(hq, (cs + a + (2 - p % 2) * da, p // 2 + 1))
            d[p // 2 + 1] = cs + a + (2 - p % 2)
        if d[p // 3] > cs + b + (p % 3) * da:
            heapq.heappush(hq, (cs + b + (p % 3) * da, p // 3))
            d[p // 3] = cs + b + (p % 3) * da
        if d[p // 3 + 1] > cs + b + (3 - p % 3) * da:
            heapq.heappush(hq, (cs + b + (3 - p % 3) * da, p // 3 + 1))
            d[p // 3 + 1] = cs + b + (3 - p % 3) * da
        if d[p // 5] > cs + c + (p % 5) * da:
            heapq.heappush(hq, (cs + c + (p % 5) * da, p // 5))
            d[p // 5] = cs + c + (p % 5) * da
        if d[p // 5 + 1] > cs + c + (5 - p % 5) * da:
            heapq.heappush(hq, (cs + c + (5 - p % 5) * da, p // 5 + 1))
            d[p // 5 + 1] = cs + c + (5 - p % 5) * da
    ans = 10 ** 25
    for k, v in d.items():
        ans = min(ans, k * da + v)
    print(ans)

Solution (Python):
import heapq
import sys
sys.setrecursionlimit(2000)
def A():
    T = int(input())
    for i in range(T):
        N, A, B, C, D = map(int, input().split())
        memo = {}
        def dfs(n):
            if n == 0:
                return 0
            if n == 1:
                return D
            if n in memo:
                return memo[n]
            l2 = (n//2)*2
            r2 = ((n+1)//2)*2
            l3 = (n//3)*3
            r3 = ((n+2)//3)*3
            l5 = (n//5)*5
            r5 = ((n+4)//5)*5
            res = n*D
            res = min(res, abs(n-l2)*D+A+dfs(l2//2))
            res = min(res, abs(n-r2)*D+A+dfs(r2//2))
            res = min(res, abs(n-l3)*D+B+dfs(l3//3))
            res = min(res, abs(n-r3)*D+B+dfs(r3//3))
            res = min(res, abs(n-l5)*D+C+dfs(l5//5))
            res = min(res, abs(n-r5)*D+C+dfs(r5//5))
            memo[n] = res
            return res
        print(dfs(N))
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
A()

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

import sys
sys.setrecursionlimit(10**7)
import math
for n,a,b,c,d in nabcd:
  memo={0:0,1:d}
  def func(i):
    if i in memo:
      return memo[i]
    ret=math.inf
    ret=min(ret,func(i//2)+a+d*(i%2))
    ret=min(ret,func((i+2-1)//2)+a+d*((2-i%2)%2))
    ret=min(ret,func(i//3)+b+d*(i%3))
    ret=min(ret,func((i+3-1)//3)+b+d*((3-i%3)%3))
    ret=min(ret,func(i//5)+c+d*(i%5))
    ret=min(ret,func((i+5-1)//5)+c+d*((5-i%5)%5))
    ret=min(ret,d*i)
    memo[i]=ret
    return ret
  print(func(n))

Solution (Python):
from functools import lru_cache

T = int(input())


def resolver(a, b, c, d):
    @lru_cache(maxsize=None)
    def _resolver(n):
        if n == 0:
            return 0
        elif n == 1:
            return d
        else:
            div5f = n // 5
            div5c = n // -5 * -1
            div3f = n // 3
            div3c = n // -3 * -1
            div2f = n // 2
            div2c = n // -2 * -1
            return min(
                d * n,
                d * abs(n - div5f * 5) + c + _resolver(div5f),
                d * abs(n - div5c * 5) + c + _resolver(div5c),
                d * abs(n - div3f * 3) + b + _resolver(div3f),
                d * abs(n - div3c * 3) + b + _resolver(div3c),
                d * abs(n - div2f * 2) + a + _resolver(div2f),
                d * abs(n - div2c * 2) + a + _resolver(div2c),
            )

    return _resolver


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

Solution (Python):
from functools import lru_cache

T = int(input())


def resolver(a, b, c, d):
    @lru_cache(maxsize=None)
    def _resolver(n):
        if n == 0:
            return 0
        elif n == 1:
            return d
        else:
            div5f = n // 5
            div5c = (n + 4) // 5
            div3f = n // 3
            div3c = (n + 2) // 3
            div2f = n // 2
            div2c = (n + 1) // 2
            return min(
                d * n,
                d * abs(n - div5f * 5) + c + _resolver(div5f),
                d * abs(n - div5c * 5) + c + _resolver(div5c),
                d * abs(n - div3f * 3) + b + _resolver(div3f),
                d * abs(n - div3c * 3) + b + _resolver(div3c),
                d * abs(n - div2f * 2) + a + _resolver(div2f),
                d * abs(n - div2c * 2) + a + _resolver(div2c),
            )

    return _resolver


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

Solution (Python):
import sys
sys.setrecursionlimit(200000)
def dfs(n):
    if n in dic.keys():
        return dic[n]
    m = n*d
    m = min(dfs((n//2))+(n-(n//2)*2)*d+a,m)
    m = min(dfs(-(-n//2))+(-(-n//2)*2-n)*d+a,m)
    m = min(dfs((n//3))+(n-(n//3)*3)*d+b,m)
    m = min(dfs(-(-n//3))+(-(-n//3)*3-n)*d+b,m)
    m = min(dfs((n//5))+(n-(n//5)*5)*d+c,m)
    m = min(dfs(-(-n//5))+(-(-n//5)*5-n)*d+c,m)
    dic[n] = m
    return m
t = int(input())
for i in range(t):
    n,a,b,c,d = map(int,input().split())
    dic = {0:0,1:d}
    print(dfs(n))

Solution (Python):
import math
from functools import lru_cache

T = int(input())


class Resolver:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    @lru_cache(maxsize=None)
    def resolve(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return self.d
        else:
            div5f = n // 5
            div5c = (n + 4) // 5
            div3f = n // 3
            div3c = (n + 2) // 3
            div2f = n // 2
            div2c = (n + 1) // 2
            return min(
                self.d * n,
                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f),
                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c),
                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f),
                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c),
                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f),
                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c),
            )


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

Solution (Python):
from functools import lru_cache

T = int(input())


def gen_dp(a, b, c, d):
    @lru_cache(maxsize=None)
    def dp(n):

        if n == 0:
            return 0
        elif n == 1:
            return d
        else:
            return min(
                d * n,
                d * abs(n - (n // 5 * 5)) + c + dp(n // 5),
                d * abs(n - ((n + 4) // 5 * 5)) + c + dp((n + 4) // 5),
                d * abs(n - (n // 3 * 3)) + b + dp(n // 3),
                d * abs(n - ((n + 2) // 3 * 3)) + b + dp((n + 2) // 3),
                d * abs(n - (n // 2 * 2)) + a + dp(n // 2),
                d * abs(n - ((n + 1) // 2 * 2)) + a + dp((n + 1) // 2),
            )

    return dp


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

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


def dfs(i):
    if i in memo:
        return memo[i]
    memo[i] = 10 ** 18
    s = d * i
    j = i // 5
    s = min(s, dfs(j) + c + d * (i - j * 5))
    j = (i + 4) // 5
    s = min(s, dfs(j) + c + d * (j * 5 - i))

    j = i // 3
    s = min(s, dfs(j) + b + d * (i - j * 3))
    j = (i + 2) // 3
    s = min(s, dfs(j) + b + d * (j * 3 - i))

    j = i // 2
    s = min(s, dfs(j) + a + d * (i - j * 2))
    j = (i + 1) // 2
    s = min(s, dfs(j) + a + d * (j * 2 - i))
    memo[i] = s
    return s


for _ in range(t):
    n, a, b, c, d = [int(i) for i in input().split()]
    memo = {}
    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, f(k + 1) + (p - r) * d + c if r else 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):
      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:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, r and f(k + 1) + p - r + 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:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, f(k + 1) + p - r + c if r else 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:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, f(k + 1) + p - r + c if r else 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):
import sys
input = sys.stdin.readline
from functools import lru_cache

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

    @lru_cache(maxsize=None)
    def calc(x):
        if x==1:
            return D

        ANS=x*D

        two=x//2*2
        if two//2<x:
            ANS=min(ANS,abs(two-x)*D+A+calc(two//2))
        if two//2+1<x:
            ANS=min(ANS,abs(two+2-x)*D+A+calc(two//2+1))

        three=x//3*3
        if three//3<x:
            ANS=min(ANS,abs(three-x)*D+B+calc(three//3))
        if three//3+1<x:
            ANS=min(ANS,abs(three+3-x)*D+B+calc(three//3+1))

        five=x//5*5
        if five//5<x:
            ANS=min(ANS,abs(five-x)*D+C+calc(five//5))
        if five//5+1<x:
            ANS=min(ANS,abs(five+5-x)*D+C+calc(five//5+1))

        return ANS

    print(calc(N))

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

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

    DP=[N*D]*(10**5)
    DP[0]=0

    for i in range(10**5):
        for k in range(i-10,i+10):
            if 0<=k<10**5 and DP[k]>DP[i]+abs(i-k)*D:
                DP[k]=DP[i]+abs(i-k)*D
        
        
            
        
        

        if 0<=2*i<10**5 and DP[2*i]>DP[i]+A:
            DP[2*i]=DP[i]+A

        if 0<=3*i<10**5 and DP[3*i]>DP[i]+B:
            DP[3*i]=DP[i]+B

        if 0<=5*i<10**5 and DP[5*i]>DP[i]+C:
            DP[5*i]=DP[i]+C

    @lru_cache(maxsize=None)
    def calc(x):
        if x<=10:
            return DP[x]

        ANS=x*D

        two=x//2*2

        ANS=min(ANS,abs(two-x)*D+A+calc(two//2))
        ANS=min(ANS,abs(two+2-x)*D+A+calc(two//2+1))

        three=x//3*3
        ANS=min(ANS,abs(three-x)*D+B+calc(three//3))
        ANS=min(ANS,abs(three+3-x)*D+B+calc(three//3+1))

        five=x//5*5
        ANS=min(ANS,abs(five-x)*D+C+calc(five//5))
        ANS=min(ANS,abs(five+5-x)*D+C+calc(five//5+1))

        return ANS

    print(calc(N))

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

@functools.lru_cache(maxsize=None)
def tk(v,a,b,c,d):
    if v == 0:
        return 9999999999
    elif v == 1:
        return d

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

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

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

t = int(input())
  
for _ in range(t):
    n,a,b,c,d = map(int,input().split())
    @lru_cache(None)
    def f(k):
      if k == 1:return d
      if k == 0:return 0
      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):
from functools import lru_cache
t=int(input())
for i in range(t):
  n,a,b,c,d=map(int,input().split())
  @lru_cache(maxsize=None)
  def f(n):
    if n==0:
      return 0
    if n==1:
      return d
    else:
      x=n*d
      
      q,r=divmod(n,2)
      if r==0:
        x=min(x,f(q)+a)
      else:
        x=min(x,f(q)+a+d,f(q+1)+a+d)
      
      q,r=divmod(n,3)
      if r==0:
        x=min(x,f(q)+b)
      elif r==1:
        x=min(x,f(q)+b+d,f(q+1)+b+d*2)
      else:
        x=min(x,f(q)+b+d*2,f(q+1)+b+d)
      
      q,r=divmod(n,5)
      if r==0:
        x=min(x,f(q)+c)
      elif r==1:
        x=min(x,f(q)+c+d,f(q+1)+c+d*4)
      elif r==2:
        x=min(x,f(q)+c+d*2,f(q+1)+c+d*3)
      elif r==3:
        x=min(x,f(q)+c+d*3,f(q+1)+c+d*2)
      else:
        x=min(x,f(q)+c+d*4,f(q+1)+c+d)
      
      return x
  
  print(f(n))

Solution (Python):
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
t=int(input())
for i in range(t):
  n,a,b,c,d=map(int,input().split())
  @lru_cache(maxsize=None)
  def f(n):
    if n==0:
      return 0
    if n==1:
      return d
    else:
      x=n*d
      
      q,r=divmod(n,2)
      if r==0:
        x=min(x,f(q)+a)
      else:
        x=min(x,f(q)+a+d,f(q+1)+a+d)
      
      q,r=divmod(n,3)
      if r==0:
        x=min(x,f(q)+b)
      elif r==1:
        x=min(x,f(q)+b+d,f(q+1)+b+d*2)
      else:
        x=min(x,f(q)+b+d*2,f(q+1)+b+d)
      
      q,r=divmod(n,5)
      if r==0:
        x=min(x,f(q)+c)
      elif r==1:
        x=min(x,f(q)+c+d,f(q+1)+c+d*4)
      elif r==2:
        x=min(x,f(q)+c+d*2,f(q+1)+c+d*3)
      elif r==3:
        x=min(x,f(q)+c+d*3,f(q+1)+c+d*2)
      else:
        x=min(x,f(q)+c+d*4,f(q+1)+c+d)
      
      return x
  
  print(f(n))

Solution (Python):
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
t=int(input())
for i in range(t):
  n,a,b,c,d=map(int,input().split())
  @lru_cache(maxsize=None)
  def f(n):
    if n==0:
      return 0
    if n==1:
      return d
    else:
      x=n*d
      
      q,r=divmod(n,2)
      if r==0:
        x=min(x,f(q)+a)
      else:
        x=min(x,f(q)+a+d,f(q+1)+a+d)
      
      q,r=divmod(n,3)
      if r==0:
        x=min(x,f(q)+b)
      elif r==1:
        x=min(x,f(q)+b+d,f(q+1)+b+d*2)
      else:
        x=min(x,f(q)+b+d*2,f(q+1)+b+d)
      
      q,r=divmod(n,5)
      if r==0:
        x=min(x,f(q)+c)
      elif r==1:
        x=min(x,f(q)+c+d,f(q+1)+c+d*4)
      elif r==2:
        x=min(x,f(q)+c+d*2,f(q+1)+c+d*3)
      elif r==3:
        x=min(x,f(q)+c+d*3,f(q+1)+c+d*2)
      else:
        x=min(x,f(q)+c+d*4,f(q+1)+c+d)
      
      return x
  
  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:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, r and f(k + 1) + p - r + 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:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, r and f(k + 1) + p - r + 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):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


t = I()
for _ in range(t):
    n, a, b, c, d = LI()
    memo = {0: 0, 1: d}
    def dfs(x):
        if x in memo:
            return memo[x]
        ret = x * d
        ret = min(ret, min(dfs(x // 2), dfs((x - 1) // 2 + 1)) + a + d * (x % 2))
        if (x % 3) < (-x % 3):
            ret = min(ret, b + dfs(x // 3) + d * (x % 3))
        else:
            ret = min(ret, b + dfs((x - 1) // 3 + 1) + d * (-x % 3))
        if (x % 5) < (-x % 5):
            ret = min(ret, c + dfs(x // 5) + d * (x % 5))
        else:
            ret = min(ret, c + dfs((x - 1) // 5 + 1) + d * (-x % 5))

        memo[x] = ret
        return ret

    print(dfs(n))