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
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

t = ni()
from functools import lru_cache

for _ in range(t):
    n,a,b,c,d = na()

    @lru_cache(None)
    def f(N):
        if N == 0:
            return 0
        if N == 1:
            return d
        ret = d * N
        q, r = divmod(N, 2)
        ret = min(ret, f(q) + a) if r==0 else min(ret, f(q) + a + d, f(q + 1) + a + d)
        q, r = divmod(N, 3)
        ret = min(ret, f(q) + b) if r == 0 else min(ret, f(q) + b + d) if r == 1 else 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
    
    print(f(n))

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

def nasu(N, n):
  if N in DP:
    return n + DP[N]
  if N == 0:
    return n
  if N == 1:
    return n + D
  ans = n + D * N
  a = N % 2
  if a == 0:
    ans = min(ans, nasu(N // 2, n + A))
  else:
    if a > 1:
      ans = min(ans, nasu((N - 1) // 2, n + D + A))
    ans = min(ans, nasu((N + 1) // 2, n + D + A))
  b = N % 3
  if b == 0:
    ans = min(ans, nasu(N // 3, n + B))
  else:
    if N > 2:
      ans = min(ans, nasu((N - b) // 3, n + (b * D) + B)) 
    ans = min(ans, nasu((N + (3 - b)) // 3, n + ((3 - b) * D) + B)) 
  c = N % 5
  if c == 0:
    ans = min(ans, nasu(N // 5, n + C))
  else:
    if N > 4:
      ans = min(ans, nasu((N - c) // 5, n + (c * D) + C))
    ans = min(ans, nasu((N + (5 - c)) // 5, n + ((5 - c) * D) + C)) 

  DP[N] = ans - n
  return ans

T = int(input())
M = [list(map(int, input().split())) for _ in range(T)]
for N, A, B, C, D in M:
  DP = {}
  ans = nasu(N, 0)
  print(ans)

Solution (Python):

from heapq import heapify, heappop, heappush, heappushpop

class PriorityQueue:
    def __init__(self, heap=None):
        '''
        heap ... list
        '''
        self.heap = heap or []
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


def solve(N,A,B,C,D):
    pq = PriorityQueue()
    visited = dict()

    best = 2 ** 63
    pq.push((0, N))

    while len(pq) > 0:
        cost, now = pq.pop()
        if now < 0:
            continue
        if now in visited and visited[now] <= cost:
            continue
        visited[now] = cost

        
        if now == 0:
            best = min(best, cost)

        for d in range(-4, 5):
            x = now + d
            c = cost + D*abs(d)
            if x == 0:
                best = min(best, c)
            if x % 5 == 0:
                minc = min(C, D*(x - x//5))
                pq.push((c+minc, x//5))

        for d in range(-2, 3):
            x = now + d
            c = cost + D*abs(d)
            if x == 0:
                best = min(best, c)
            if x % 3 == 0:
                minc = min(B, D*(x - x//3))
                pq.push((c+minc, x//3))

        for d in range(-1, 2):
            x = now + d
            c = cost + D*abs(d)
            if x == 0:
                best = min(best, c)
            if x % 2 == 0:
                minc = min(A, D*(x - x//2))
                pq.push((c+minc, x//2))

    return best

if __name__ == '__main__':
    T = int(input())
    for t in range(T):
        N,A,B,C,D = map(int, input().split(' '))
        print(solve(N,A,B,C,D))

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

dp={}
def f(n, a, b, c, d):
    

    if n in dp:
        return dp[n]
    
    if n==0:
        dp[n]=10**20
        return dp[n]
    if n==1:
        dp[n]=d
        return dp[n]








    
    l=[d*n]
    if n%2==0:

        l.append(f(n//2,a,b,c,d)+a)
        
        x=(n+1)//3*3
        dx=abs(x-n)

        l.append(f(x//3,a,b,c,d)+b+dx*d)
        
        x=(n+2)//5*5
        dx=abs(x-n)
        l.append(f(x//5,a,b,c,d)+c+dx*d)
    else:
        l.append(f((n-1)//2, a,b,c,d)+a+d)
        l.append(f((n+1)//2, a,b,c,d)+a+d)
        
        x=(n+1)//3*3
        dx=abs(x-n)
        l.append(f(x//3,a,b,c,d)+b+dx*d)
        
        x=(n+2)//5*5
        dx=abs(x-n)
        l.append(f(x//5,a,b,c,d)+c+dx*d)

    dp[n]=min(l)
    return dp[n]

def solve(n,a,b,c,d):
    print(f(n,a,b,c,d))
    
    

for tc in testcase:
    solve(*tc)
    dp.clear()

Solution (Python):
import sys
from heapq import heappush, heappop
from collections import defaultdict

input = sys.stdin.readline
T = int(input())
NABCD = [list(map(int,input().split())) for i in range(T)]

for N,A,B,C,D in NABCD:
    h = [(N,0)]
    ans = D*N
    dic = defaultdict(lambda:D*N+1)
    while h:
        val, cost = heappop(h)

        if ans <= cost:
            continue

        if dic[val] <= cost:
            continue
        dic[val] = cost

        if val == 0:
            ans = min(ans,cost)
            continue
        if val == 1:
            ans = min(ans,cost+D)
            continue

        heappush(h,(0,cost + val*D))
        m2 = val % 2
        if m2 == val:
            heappush(h,(0,cost+D))
        elif m2 == 0:
            heappush(h,(val//2,cost+A))
        else:
            heappush(h,((val+1)//2,cost+A+D))
            heappush(h,((val-1)//2,cost+A+D))
        
        m3 = val % 3
        if m3 == val:
            heappush(h,(0,cost+m3*D))
        elif m3 == 0:
            heappush(h,(val//3,cost+B))
        else:
            heappush(h,((val-m3)//3,cost+B+m3*D))
            heappush(h,((val+3-m3)//3,cost+B+(3-m3)*D))

        m5 = val % 5
        if m5 == val:
            heappush(h,(0,cost+m5*D))
        elif m5 == 0:
            heappush(h,(val//5,cost+C))
        else:
            heappush(h,((val-m5)//5,cost+C+m5*D))
            heappush(h,((val+5-m5)//5,cost+C+(5-m5)*D))
    print(ans)

Solution (Python):
from functools import lru_cache
import sys
 
sys.setrecursionlimit(10 ** 9)
 
t = int(input())
 
for _ in range(t):
  n,a,b,c,d = map(int, input().split())
  
  dic = {0:0, 1:d}
  @lru_cache(maxsize = None)
  def f(n):
    if n in dic:
      return dic[n]
    
    nn = n * d
    
    n5 = (n % 5) * d + c + f(n // 5)
    if n % 5 != 0:
      
      n5 = min(n5, (-n % 5) * d + c + f((n // 5) + 1))
    n3 = (n % 3) * d + b + f(n // 3)
    if n % 3 != 0:
      n3 = min(n3, (-n % 3) * d + b + f((n // 3) + 1))
    n2 = (n % 2) * d + a + f(n // 2)
    if n % 2 != 0:
      n2 = min(n2, (n % 2) * d + a + f((n // 2) + 1))

    ret = min(nn, n2, n3, n5)
    dic[n] = ret
    return ret
 
  print(f(n))

Solution (Python):
def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

used = {}
used[0] = 0
gg = {}

def dfs(n, a, b, c, d):
    global used
    
    if n in used: return used[n]
    ret = n*d
    for i in range(-4, 4):
        now = n + i
        if now%2==0 and now > 0 and abs(i) < 2: ret = min(ret, abs(i)*d + a + dfs(now//2, a, b, c, d))
        if now%3==0 and now > 0 and abs(i) < 3: ret = min(ret, abs(i)*d + b + dfs(now//3, a, b, c, d))
        if now%5==0 and now > 0: ret = min(ret, abs(i)*d + c + dfs(now//5, a, b, c, d))
    used[n] = ret
    return ret
        


def solve():
    n,a,b,c,d = NextInts()
    global used
    used = {}
    gg = {}
    used[0] = 0
    used[1] = d
    used[2] = min(d*2, d+a)
    return dfs(n, a, b, c,d)
    
def main():
    t = NextInt()
    ans = [solve() for i in range(t)]
    for i in range(t):
        print(ans[i])

if __name__ == "__main__":
    main()

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

hpush = heapq.heappush
hpop = heapq.heappop
for _ in [0]*T:
    ans = 10**18
    N,A,B,C,D = map(int,input().split())
    hq = [(0,N)]
    made = set()
    while hq:
        cost,n = hpop(hq)
        if n==0:
            ans = min(ans,cost)
            continue
        if n in made:continue
        made.add(n)

        n2 = n//2
        cost2 = cost + min(D*(n-n2),A+D*(n%2))
        hpush(hq,(cost2,n2))

        n2b = (n-1)//2+1
        cost2b = cost + min(D*(n-n2b),A+D*((-n)%2))
        hpush(hq,(cost2b,n2b))

        n3 = n//3
        cost3 = cost + min(D*(n-n3),B+D*(n%3))
        hpush(hq,(cost3,n3))

        n3b = (n-1)//3+1
        cost3b = cost + min(D*(n-n3b),B+D*((-n)%3))
        hpush(hq,(cost3b,n3b))

        n5 = n//5
        cost5 = cost + min(D*(n-n5),C+D*(n%5))
        hpush(hq,(cost5,n5))
        
        n5b = (n-1)//5+1
        cost5b = cost + min(D*(n-n5b),C+D*((-n)%5))
        hpush(hq,(cost5b,n5b))

    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    INF = float('inf')
    mem = {}
    def solve(n):
        if n==0: return 0
        if n==1: return D
        if n in mem: return mem[n]
        tmp = n*D
        if n%2==0:
            tmp = min(tmp, solve(n//2) + A)
        else:
            tmp = min(tmp, solve(n//2) + A+D, solve(n//2+1) + A+D)
        if n%3==0:
            tmp = min(tmp, solve(n//3) + B)
        else:
            d = n%3
            u = 3-d
            tmp = min(tmp, solve(n//3) + B+d*D, solve(n//3+1) + B+u*D)
        if n%5==0:
            tmp = min(tmp, solve(n//5) + C)
        else:
            d = n%5
            u = 5-d
            tmp = min(tmp, solve(n//5) + C+d*D, solve(n//5+1) + C+u*D)
        mem[n] = tmp
        return tmp
    print(solve(N))

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


inf = float('Inf')
f = [2, 3, 5]
cost = [0]*4


d = dict()


def dfs(x, d):
    if x in d:
        return(d[x])
    ret = cost[-1]*x
    for i in range(3):
        if x < f[i]:
            continue
        if x % f[i] == 0:
            ret = min(ret, dfs(x // f[i], d) + cost[i])
        else:
            k = x // f[i]
            ret = min(ret, cost[i] + dfs(k, d) + (x %
                                                  f[i]) * cost[-1], cost[i] + dfs(k+1, d) + ((k+1)*f[i]-x)*cost[-1])
    d[x] = ret
    return(ret)


def main():
    T = int(input())
    for _ in range(T):
        N, *c = map(int, input().split())
        for i in range(4):
            cost[i] = c[i]
        print(dfs(N, dict()))


main()

Solution (Python):
mod = 1000000007
eps = 10 ** -9
inf = 10 ** 40


def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline

    for t in range(int(input())):
        N, a, b, c, d = map(int, input().split())
        que = []

        heappush(que, -N)
        seen = {N: 0}
        while que:
            n = -heappop(que)
            if n == 1:
                seen[0] = seen[1] + d
                break
            
            n2_minor = n // 2
            if n % 2 == 0:
                if n2_minor not in seen:
                    seen[n2_minor] = seen[n] + min(a, n2_minor * d)
                    heappush(que, -n2_minor)
                else:
                    seen[n2_minor] = min(seen[n2_minor], seen[n] + min(a, n2_minor * d))
            else:
                if n2_minor not in seen:
                    seen[n2_minor] = seen[n] + min(a, n2_minor * d) + d
                    heappush(que, -n2_minor)
                else:
                    seen[n2_minor] = min(seen[n2_minor], seen[n] + min(a, n2_minor * d) + d)
                n2_major = n2_minor + 1
                if n2_major not in seen:
                    seen[n2_major] = seen[n] + min(a, n2_major * d) + d
                    heappush(que, -n2_major)
                else:
                    seen[n2_major] = min(seen[n2_major], seen[n] + min(a, n2_major * d) + d)

            
            n3_minor = n // 3
            if n % 3 == 0:
                if n3_minor not in seen:
                    seen[n3_minor] = seen[n] + min(b, n3_minor * 2 * d)
                    heappush(que, -n3_minor)
                else:
                    seen[n3_minor] = min(seen[n3_minor], seen[n] + min(b, n3_minor * 2 * d))
            else:
                mod3 = n % 3
                if n3_minor not in seen:
                    seen[n3_minor] = seen[n] + min(b, n3_minor * 2 * d) + d * mod3
                    heappush(que, -n3_minor)
                else:
                    seen[n3_minor] = min(seen[n3_minor], seen[n] + min(b, n3_minor * 2 * d) + d * mod3)
                n3_major = n3_minor + 1
                if n3_major not in seen:
                    seen[n3_major] = seen[n] + min(b, n3_major * 2 * d) + d * (3 - mod3)
                    heappush(que, -n3_major)
                else:
                    seen[n3_major] = min(seen[n3_major], seen[n] + min(b, n3_major * 2 * d) + d * (3 - mod3))

            
            n5_minor = n // 5
            if n % 5 == 0:
                if n5_minor not in seen:
                    seen[n5_minor] = seen[n] + min(c, d * n5_minor * 4)
                    heappush(que, -n5_minor)
                else:
                    seen[n5_minor] = min(seen[n5_minor], seen[n] + min(c, d * n5_minor * 4))
            else:
                mod5 = n % 5
                if n5_minor not in seen:
                    seen[n5_minor] = seen[n] + min(c, d * n5_minor * 4) + d * mod5
                    heappush(que, -n5_minor)
                else:
                    seen[n5_minor] = min(seen[n5_minor], seen[n] + min(c, d * n5_minor * 4) + d * mod5)
                n5_major = n5_minor + 1
                if n5_major not in seen:
                    seen[n5_major] = seen[n] + min(c, d * n5_major * 4) + d * (5 - mod5)
                    heappush(que, -n5_major)
                else:
                    seen[n5_major] = min(seen[n5_major], seen[n] + min(c, d * n5_major * 4) + d * (5 - mod5))
        print(seen[0])
        
        


if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache
import sys

sys.setrecursionlimit(10**6)


@lru_cache(maxsize=None)
def dp(n):
    if n == 1:
        return D
    cand = []
    if n % 2 == 0:
        cand.append(dp(n // 2) + A)
    if n % 2 == 1:
        cand.append(dp((n-1) // 2) + A + D)
        cand.append(dp((n+1) // 2) + A + D)
    if n % 3 == 0:
        cand.append(dp(n // 3) + B)
    if n % 3 == 1:
        cand.append(dp((n-1) // 3) + B + D)
        cand.append(dp((n+2) // 3) + B + 2 * D)
    if n % 3 == 2:
        cand.append(dp((n+1) // 3) + B + D)
        if n - 2 != 0:
            cand.append(dp((n-2) // 3) + B + 2 * D)
    if n % 5 == 0:
        cand.append(dp(n // 5) + C)
    if n % 5 == 1:
        cand.append(dp((n-1) // 5) + C + D)
        cand.append(dp((n+4) // 5) + C + 4 * D)
    if n % 5 == 2:
        if n - 2 != 0:
            cand.append(dp((n-2) // 5) + C + 2 * D)
        cand.append(dp((n+3) // 5) + C + 3 * D)
    if n % 5 == 3:
        if n - 3 != 0:
            cand.append(dp((n-3) // 5) + C + 3 * D)
        cand.append(dp((n+2) // 5) + C + 2 * D)
    if n % 5 == 4:
        cand.append(dp((n+1) // 5) + C + D)
        if n - 4 != 0:
            cand.append(dp((n-4) // 5) + C + 4 * D)
    cand.append(D * n)
    return min(cand)


T = int(input())
for i in range(T):
    N, A, B, C, D = [int(_) for _ in input().split()]
    dp.cache_clear()
    print(dp(N))

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):
    if N == 1:
        return D

    @lru_cache(maxsize=None)
    def f(n):
        ans = n*D
        for i in range(-5, 6 if n > 10 else 1):
            m = n + i
            i = abs(i)
            if m < 0:
                continue
            if m == 0:
                ans = min(ans, D*i)
                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):
def dfs(N, A, B, C, D, memo):
    if (N in memo):
        return memo[N]
    
    if (N == 0):
        return 0
    
    if (N == 1):
        return D
    
    ans = N * D
    if (N % 2 == 0):
        ans = min(ans, dfs(N // 2, A, B, C, D, memo) + A)
    else:
        rem = N % 2
        ans = min(ans, dfs((N - rem) // 2, A, B, C, D, memo) + A + rem * D)
        ans = min(ans, dfs((N + 2 - rem) // 2, A, B, C, D, memo) + A + (2 - rem) * D)
    
    if (N % 3 == 0):
        ans = min(ans, dfs(N // 3, A, B, C, D, memo) + B)
    else:
        rem = N % 3
        ans = min(ans, dfs((N - rem) // 3, A, B, C, D, memo) + B + rem * D)
        ans = min(ans, dfs((N + 3 - rem) // 3, A, B, C, D, memo) + B + (3 - rem) * D)
    
    if (N % 5 == 0):
        ans = min(ans, dfs(N // 5, A, B, C, D, memo) + C)
    else:
        rem = N % 5
        ans = min(ans, dfs((N - rem) // 5, A, B, C, D, memo) + C + rem * D)
        ans = min(ans, dfs((N + 5 - rem) // 5, A, B, C, D, memo) + C + (5 - rem) * D)
    
    memo[N] = ans
    return ans


def solve(N, A, B, C, D):
    memo = dict()
    ans = dfs(N, A, B, C, D, memo)
    print(ans)


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

Solution (Python):
import heapq

ans = []

T = int(input())
for i in range(T):
    N,A,B,C,D = map(int,input().split())
    Q = {}
    queue = []
    for i in range(N,N+1):
        Q[i] = abs(i-N)*D
        heapq.heappush(queue,-i)
    while 1:
        q = -heapq.heappop(queue)
        if q == 0:
            break
        a = q//2
        b = q//3
        c = q//5
        a_V = min(Q[q]+A+D*(q%2),Q[q]+(q-a)*D)
        b_V = min(Q[q]+B+D*(q%3),Q[q]+(q-b)*D)
        c_V = min(Q[q]+C+D*(q%5),Q[q]+(q-c)*D)
        a_2 = (q+1)//2
        b_2 = (q+2)//3
        c_2 = (q+4)//5
        a_V_2 = min(Q[q]+(a_2*2-q)*D+A,Q[q]+abs(q-a_2)*D)
        b_V_2 = min(Q[q]+(b_2*3-q)*D+B,Q[q]+abs(q-b_2)*D)
        c_V_2 = min(Q[q]+(c_2*5-q)*D+C,Q[q]+abs(q-c_2)*D)
        
        if a in Q:
            if Q[a] > a_V:
                Q[a] = a_V
        else:
            heapq.heappush(queue,-a)
            Q[a] = a_V
        
        if b in Q:
            if Q[b] > b_V:
                Q[b] = b_V
        else:
            heapq.heappush(queue,-b)
            Q[b] = b_V        
        
        if c in Q:
            if Q[c] > c_V:
                Q[c] = c_V
        else:
            heapq.heappush(queue,-c)
            Q[c] = c_V

        if a_2 in Q:
            if Q[a_2] > a_V_2:
                Q[a_2] = a_V_2
        else:
            heapq.heappush(queue,-a_2)
            Q[a_2] = a_V_2
        
        if b_2 in Q:
            if Q[b_2] > b_V_2:
                Q[b_2] = b_V_2
        else:
            heapq.heappush(queue,-b_2)
            Q[b_2] = b_V_2
        
        if c_2 in Q:
            if Q[c_2] > c_V_2:
                Q[c_2] = c_V_2
        else:
            heapq.heappush(queue,-c_2)
            Q[c_2] = c_V_2

        
        
    
    ans.append(Q[0])
for i in ans:
    print(i)

Solution (Python):
from heapq import heappush, heappop
from collections import defaultdict

def small(N, A, B, C, D):
    if N == 1:
        return D
    elif N == 2:
        return min(2*D, D+A)
    elif N == 3:
        return min(3*D, D+B, 2*D+A)
    else:
        assert False

def solve(N, A, B, C, D):
    if N <= 3:
        return small(N, A, B, C, D)
    visited = set()
    
    dist = {}
    dist[N] = 0
    q = []
    heappush(q, (0, N))
    def update(d2, d, cost):
        nonlocal q
        nonlocal dist
        if not d2 in dist or dist[d2] > dist[d] + cost:
            dist[d2] = dist[d] + cost
            heappush(q, (dist[d2], d2))
            
            
    while len(q) > 0:
        _prov_cost, d = heappop(q)
        if d in visited:
            continue
        else:
            visited.add(d)
        
        mod2 = d % 2
        mod3 = d % 3
        mod5 = d % 5
        if mod2 == 0:
            update(d//2, d, A)
        if mod3 == 0:
            update(d//3, d, B)
        if mod5 == 0:
            update(d//5, d, C)
        
            
        
        
        
        update((d-1)//2, d, min(D+A, (d - (d-1)//2)*D))
        
        update((d+1)//2, d, min(D+A, (d - (d+1)//2)*D))
        
        _d2 = (d-mod3)//3
        update(_d2, d, min(mod3*D+B, (d-_d2)*D))
        _d2 = (d+(3-mod3))//3
        update(_d2, d, min((3-mod3)*D+B, (d-_d2)*D))
        
        _d2 = (d-mod5)//5
        update(_d2, d, min(mod5*D+C, (d-_d2)*D))
        _d2 = (d+(5-mod5))//5
        update(_d2, d, min((5-mod5)*D+C, (d-_d2)*D))
        '''
        if d % 5 == 1:
            update((d-1)//3, D+C)
            update((d+4)//5, 4*D+C)
        elif d % 5 == 2:
            update((d-2)//3, 2*D+C)
            update((d+3)//5, 3*D+C)
        '''

        
        
        
    
    return dist[0]
            
            

    

    

def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = tuple(int(c) for c in input().split(' '))
        print(solve(N, A, B, C, D))

if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    pq = [(0, N)]
    used = set()
    while pq:
        c, x = heappop(pq)
        if x in used:
            continue
        used.add(x)
        if x == 1:
            print(c + D)
            break
        heappush(pq, (c + D * (x - 1), 1))
        if x % 2 == 0:
            heappush(pq, (c + A, x // 2))
        else:
            heappush(pq, (c + D + A, (x - 1) // 2))
            heappush(pq, (c + D + A, (x + 1) // 2))
        if x >= 3:
            if x % 3 == 0:
                heappush(pq, (c + B, x // 3))
            else:
                heappush(pq, (c + D * (x % 3) + B, x // 3))
                heappush(pq, (c + D * (3 - x % 3) + B, x // 3 + 1))
        if x >= 5:
            if x % 5 == 0:
                heappush(pq, (c + C, x // 5))
            else:
                heappush(pq, (c + D * (x % 5) + C, x // 5))
                heappush(pq, (c + D * (5 - x % 5) + C, x // 5 + 1))
        else:
            heappush(pq, (c + D * (5 - x) + C, 1))

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

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, b, c, d, a = nm()
    g = dict()
    def calc(x):
        if x < 2:
            return a * x
        if x in g:
            return g[x]
        y1 = x // 5
        ret1 = min(a * (x % 5) + d, a * (x - y1)) + calc(y1)
        y2 = (x - 1)//5 + 1
        ret2 = min(a * (y2 * 5 - x) + d, a * (x - y2)) + calc(y2)
        y3 = x // 3
        ret3 = min(a * (x % 3) + c, a * (x - y3)) + calc(y3)
        y4 = (x - 1)//3 + 1
        ret4 = min(a * (y4 * 3 - x) + c, a * (x - y4)) + calc(y4)
        y5 = x // 2
        ret5 = min(a * (x % 2) + b, a * (x - y5)) + calc(y5)
        y6 = (x - 1)//2 + 1
        ret6 = min(a * (y6 * 2 - x) + b, a * (x - y6)) + calc(y6)
        g[x] = min([ret1, ret2, ret3, ret4, ret5, ret6])
        return g[x]
    print(calc(n))
    return

T = ni()
for _ in range(T):
    solve()

Solution (Python):
memo = {}

bases = [2, 3, 5]
baseCost = [-1, -1, -1]
d = -1

def getAns(x):
    if x == 0:
        return 0
    if x in memo:
        return memo[x]
    memo[x] = -1
    ans = x * d
    for k in range(3):
        for delta in range(-bases[k] + 1, bases[k]):
            afterMul = x + delta
            if afterMul >= 0 and afterMul % bases[k] == 0:
                if afterMul // bases[k] in memo and memo[afterMul // bases[k]] == -1:
                    continue
                ans = min(ans, getAns(afterMul // bases[k]) + abs(delta) * d + baseCost[k])
    memo[x] = ans
    return ans

t = int(input())
for i in range(t):
    memo = {}
    n, a, b, c, dx = map(int, input().split())
    baseCost = [a, b, c]
    d = dx
    print(getAns(n))

Solution (Python):

from collections import defaultdict
T = int(input())


def dfs(n, b):

    if dp[n] != 0:
        return dp[n]

    if n == 1:
        return D
    elif n == 0:
        return 0

    ans = 10**30

    
    if n % 2 != 0:
        t = n // 2 * 2 + 2
        tmp = dfs(t // 2, n) + min(A, t // 2 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)
        t = n // 2 * 2 + 0
        tmp = dfs(t // 2, n) + min(A, t // 2 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)
    elif n % 2 == 0:
        t = n
        tmp = dfs(t // 2, n) + min(A, t // 2 * D)
        ans = min(ans, tmp)

    
    if n % 3 != 0:
        t = n // 3 * 3 + 3
        tmp = dfs(t // 3, n) + min(B, t // 3 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)
        t = n // 3 * 3 + 0
        tmp = dfs(t // 3, n) + min(B, t // 3 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)
    else:
        t = n
        tmp = dfs(t // 3, n) + min(B, t // 3 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)

    
    if n % 5 != 0:
        t = n // 5 * 5 + 5
        tmp = dfs(t // 5, n) + min(C, t // 5 * 4 * D) + D * abs(n - t)
        ans = min(ans, tmp)

        t = n // 5 * 5 + 0
        tmp = dfs(t // 5, n) + min(C, t // 5 * 4 * D) + D * abs(n - t)
        ans = min(ans, tmp)
    else:
        t = n
        tmp = dfs(t // 5, n) + min(C, t // 5 * 4 * D) + D * abs(n - t)
        ans = min(ans, tmp)

    dp[n] = ans

    return ans


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

    dp = defaultdict(int)
    print(dfs(N, -1))

Solution (Python):
costs = {}
searching = {}

def init(a, b, c, d):
    my_costs = {}
    my_costs[0] = 0
    frontier = set([0])
    for depth in range(8):
        new_frontier = set()
        for f in frontier:
            for ff, cst in [(f*2, a), (f*3, b), (f*5, c), (f-1, d), (f+1, d)]:
                if ff < 0:
                    continue
                if ff not in my_costs:
                    my_costs[ff] = my_costs[f] + cst
                else:
                    my_costs[ff] = min(my_costs[f] + cst, my_costs[ff])
                new_frontier.add(ff)
        frontier = new_frontier
    for k in range(20):
        costs[k] = my_costs[k]

def solve(n, a, b, c, d):
    if n in costs:
        return costs[n]

    next_step = {}
    for delta in range(-5, 5+1):
        m = n + delta
        for div, div_cost in [(2, a), (3, b), (5, c)]:
            if m % div == 0:
                cst = d * abs(delta) + div_cost
                r = m // div
                if r not in next_step:
                    next_step[r] = cst
                else:
                    next_step[r] = min(next_step[r], cst)

    
    costs_lst = []
    for r in next_step:
        cst = solve(r, a, b, c, d) + next_step[r]
        costs_lst.append(cst)
    costs[n] = min(costs_lst + [n*d])
    return costs[n]

t = int(input())

for casenum in range(1, t+1):
    n, a, b, c, d = map(int, input().split())
    costs = {}
    searching = {}

    init(a, b, c, d)
    answer = solve(n, a, b, c, d)
    
    print(answer)

Solution (Python):
from collections import defaultdict as dd, deque

t = int(input())

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

    todo = [(n, 0)]

    best = 10**100
    cheap = dd(lambda: 10**100)
    while todo:
        
        x,cost = todo.pop()
        if x < 0 or cost >= best:
            continue
        if x == 0:
            best = min(best, cost)
            continue
        if x in cheap and cheap[x] <= cost:
            continue
        cheap[x] = cost

        todo.append((0, cost + x*d))
        for i in range(x-1, x+2):
            if i%2 == 0:
                dist = abs(i - x)
                todo.append((i//2, cost + dist*d + a))
        for i in range(x-2, x+3):
            if i%3 == 0:
                dist = abs(i - x)
                todo.append((i//3, cost + dist*d + b))
        for i in range(x-4, x+5):
            if i%5 == 0:
                dist = abs(i - x)
                todo.append((i//5, cost + dist*d + c))
    print(best)