Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

inputs = input().split(' ')
N = int(inputs[0])
M = int(inputs[1])
cards = input().split(' ')
cards = [int(x) for x in cards]

for _ in range(M):
    inputs = input().split(' ')
    B = int(inputs[0])
    C = int(inputs[1])
    min_idx  = np.argmin(cards)
    for _ in range(B):
        if cards[min_idx] >= C:
            break
        else:
            cards[min_idx] = C
            min_idx = np.argmin(cards)

print(sum(cards))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

inputs = input().split(' ')
N = int(inputs[0])
M = int(inputs[1])
cards = input().split(' ')
cards = [int(x) for x in cards]
cards.sort()

BC = []
for _ in range(M):
    inputs = input().split(' ')
    inputs = [int(x) for x in inputs]
    BC.append({'B': inputs[0], 'C': inputs[1]})

idx = 0
BC.sort(key=lambda x: x['C'], reverse=True)
for bc in BC:
    if idx >= N:
        break
    for _ in range(bc['B']):
        c = bc['C']
        if cards[idx] >= c:
            break
        else:
            cards[idx] = c
            idx += 1
            if idx >= N:
                break

print(sum(cards))
### BUGGY CODE ###

N, W = map(int, input().split(" "))
items = [tuple(map(int, input().split(" "))) for _ in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(1, W+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split(" "))
#items = [tuple(map(int, input().split(" "))) for _ in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
    w, v = map(int, input().split(" "))
    for j in range(1, W+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])
### BUGGY CODE ###

H, W = map(int, input().split())
AB = []
max_ab = 0
for i in range(H):
  AB.append(list(map(int, input().split())))
  max_ab = max(max_ab, max(AB[-1]))

for i in range(H):
  AB[i] = [abs(AB[i][j] - int(b)) for j, b in enumerate(input().split())]

K = max_ab*(H + W) + 1
dp = [[[False]*K for w in range(W+1)] for h in range(H+1)]
dp[0][0][0] = True
dp[0][1][0] = True
dp[1][0][0] = True

for h in range(H):
  for w in range(W):
    ab = AB[h][w]
    for i, tp in enumerate(dp[h][w+1]):
      if not tp:
        continue
        
      dp[h+1][w+1][abs(i+ab)] = True
      dp[h+1][w+1][abs(i-ab)] = True
      
    for i, tp in enumerate(dp[h+1][w]):
      if not tp:
        continue
      
      dp[h+1][w+1][abs(i+ab)] = True
      dp[h+1][w+1][abs(i-ab)] = True

for k in range(K):
  if dp[H][W][k]:
    print(k)
    break

### FIXED CODE ###

H, W = map(int, input().split())
AB = []
max_ab = 0
for i in range(H):
  AB.append(list(map(int, input().split())))
  max_ab = max(max_ab, max(AB[-1]))

for i in range(H):
  AB[i] = [abs(AB[i][j] - int(b)) for j, b in enumerate(input().split())]

base = max_ab*(H + W)
dp = [[1 << base for w in range(W)] for h in range(H)]
dp[0][0] = (1 << base + AB[0][0]) | (1 << base - AB[0][0])
for h in range(1, H):
  dp[h][0] = (dp[h-1][0] << AB[h][0]) | (dp[h-1][0] >> AB[h][0])

for w in range(1, W):
  dp[0][w] = (dp[0][w-1] << AB[0][w]) | (dp[0][w-1] >> AB[0][w])

for h in range(1, H):
  for w in range(1, W):
    dp[h][w] = (
      (dp[h-1][w] << AB[h][w]) | (dp[h-1][w] >> AB[h][w]) 
      | (dp[h][w-1] << AB[h][w]) | (dp[h][w-1] >> AB[h][w]))

positive = bin(dp[H-1][W-1] >> base)
print(positive[::-1].find('1'))
### BUGGY CODE ###

import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    K, S = il()
    print([x+y+z for x in range(K + 1) for y in range(K + 1) for z in range(K+1)].count(S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    K, S = map(int, sys.stdin.readline().split())

    ret = 0
    for x in range(K + 1):
        for y in range(K + 1):
            if S - x - y <= K and S - x - y >= 0:
                ret += 1
    print(ret)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

for i in range(n):
    if done[i]==1:
        continue
    for j in range(i+1,n):
        if done[j]==1:
            continue
        elif li[j]%li[i]==0:
            done[j]=1
            dp[j]=0
            if li[j]==li[i]:
                done[i]=1
                dp[i]=0

            
print(sum(dp))

### FIXED CODE ###

n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)
### BUGGY CODE ###

import copy


def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [0 for i in range(t)]
    ls = [[] for i in range(t)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0 and dp[j - f[i][0]] + f[i][1] > dp[j]:
                dp[j] = dp[j - f[i][0]] + f[i][1]
                ls[j] = copy.copy(ls[j - f[i][0]])
                ls[j].append(i)
    res = dp[t - 1]
    ll = ls[t - 1]
    fff = [0 for _ in range(n)]
    for sll in ll:
        fff[sll] = 1
    ff = [f[i][1] for i in range(n) if fff[i] == 0]
    if ff:
        return res + max(ff)
    else:
        return res


print(main())


### FIXED CODE ###



def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp1 = [[0 for i in range(t)]for j in range(n+1)]
    dp2 = [[0 for i in range(t)]for j in range(n+1)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0:
                dp1[i+1][j] = max(dp1[i][j - f[i][0]] + f[i][1],dp1[i][j])
            else:
                dp1[i+1][j] = dp1[i][j]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[n-1-i][0] >= 0:
                dp2[i+1][j] = max(dp2[i][j - f[n-1-i][0]] + f[n-1-i][1],dp2[i][j])
            else:
                dp2[i+1][j] = dp2[i][j]

    res = 0
    for i in range(n):
        for j in range(t):
            res = max(res,dp1[i][j]+f[i][1]+dp2[n-1-i][t-1-j])

    return res




print(main())
### BUGGY CODE ###

n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]
        if dp[miru-1] == n-1:
          flag = False
          break
        else:
          if B[miru-1] != 1:
            if L[miru-1][dp[miru-1]][1] == i+1:
              dp[i] += 1
              dp[miru-1] += 1
              B[miru-1] = 1
              act += 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  if cnt >= 50000:
    dp = [n-1]*n
    flag = False
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

### FIXED CODE ###

import time
start = time.time()
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          dp = [n-1]*n
        else:
          if B[miru] != 1:
            if L[miru][dp[miru]][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              if act == 0:
                act = 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
  ela = time.time()-start
  if ela > 1.7:
    dp = [n-1]*n
if flag == False:
  print(-1)
else:
  if ela < 1.7:
    print(cnt)
  else:
    print(n*(n-1)//2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import itertools
 
n, m, d = map(int, input().split())

# 重複順列で全パターン出す
nm = list(itertools.product([i for i in range(1, n+1)], repeat=m))

avg = []
for tmp in nm:
    bty = 0
    for i in range(m-1):
        if abs(tmp[i] - tmp[i+1]) == d:
            bty += 1
    avg.append(bty)

print(sum(avg) / len(nm))

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n, m, d = map(int, input().split())

if d == 0:
    print(1 / n * (m - 1))

else:
    print((2 * (n - d) / n ** 2) * (m - 1))
### BUGGY CODE ###

#encoding utf-8

N, M, Q = map(int, input().split())

L = []
R = []
for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

p = []
q = []

for i in range(Q):
    pa, qa = map(int, input().split())
    p.append(pa)
    q.append(qa)

def Answer(i):
    count = 0
    for j in range(M):
        if p[i] <= L[j] and R[j] <= q[i]:
            count += 1
    return count

for i in range(Q):
    print(Answer(i))


### FIXED CODE ###


N, M, Q = map(int, input().split())
rail = []
for i in range(M):
    r = list(map(int, input().split()))
    rail.append(r)
 
query = []
for i in range(Q):
    q = list(map(int, input().split()))
    query.append(q)
 
f = [[0 for i in range(N)] for j in range(N)]
g = [[0 for i in range(N)] for j in range(N)]
 
for i in range(M):
    f[rail[i][0]-1][rail[i][1]-1] += 1
 
for i in range(N):
    j = 0
    while j + i < N:
        if i == 0:
            g[j][j+i] = f[j][j+i]
        else:
            g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
        j += 1
 
for i in range(Q):
    print(g[query[i][0]-1][query[i][1]-1])
### BUGGY CODE ###

S = input()
T = input()

dicS = {}
dicT = {}

for i,_s_ in enumerate(S):
   if not _s_ in dicS:
       dicS[_s_] = []
   dicS[_s_] = dicS[_s_] + [i]
   
for i,_t_ in enumerate(T):
    if not _t_ in dicT:
        dicT[_t_] = []
    dicT[_t_] = dicT[_t_] + [i]
    
listS = []
listT = []

for _s_ in dicS.values():
    listS.append(_s_)
    
for _t_ in dicT.values():
    listT.append(_t_)

for i,_s_ in enumerate(listS):
    listS[i] = tuple(_s_)
    
for i,_t_ in enumerate(listT):
    listT[i] = tuple(_t_)


setS = set(listS)
setT = set(listT)

if setS == setT:
   print('Yes')
else:
    print('No')

### FIXED CODE ###

S = input()
T = input()
 
dicS = {}
dicT = {}

alphabet = "abcdefghijklmnopqrstuvwxyz"

for _a in alphabet:
    dicS[_a] = []
    dicT[_a] = []

for i,_s_ in enumerate(S):
    dicS[_s_].append(i)
   
for i,_t_ in enumerate(T):
    dicT[_t_].append(i)

for _s in dicS:
    dicS[_s] = tuple(dicS[_s])

for _t in dicT:
    dicT[_t] = tuple(dicT[_t])

flg = True
for t in dicS.values():
    if not t in dicT.values():
        flg = False
        
if flg:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Cake 123
https://atcoder.jp/contests/abc123/tasks/abc123_d

"""
import sys


from itertools import product

def solve(X, Y, Z, K, A, B, C):
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    while len(A)-1 * len(B)-1 * len(C)-1 > K:
        m = sorted([[A[0], 'a'], [B[0], 'b'], [C[0], 'c']])
        _, mi = m.pop(0)
        if mi == 'a':
            A.pop(0)
        elif mi == 'b':
            B.pop(0)
        else:
            C.pop(0)

    return sorted([sum(p) for p in product(A, B, C)], reverse=True)[:K]


def main(args):
    X, Y, Z, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]
    C = [int(c) for c in input().split()]
    ans = solve(X, Y, Z, K, A, B, C)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Cake 123
https://atcoder.jp/contests/abc123/tasks/abc123_d

"""
import sys


from itertools import product

def solve(X, Y, Z, K, A, B, C):
    # TLE
    res_AB = sorted([sum(p) for p in product(A, B)], reverse=True)[:K]
    return sorted([sum(p) for p in product(res_AB, C)], reverse=True)[:K]


def main(args):
    X, Y, Z, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]
    C = [int(c) for c in input().split()]
    ans = solve(X, Y, Z, K, A, B, C)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

n = int(input())
d = [int(i) for i in input().split()]
m = int(input())
t = [int(i) for i in input().split()]
d.sort()
t.sort()
idx = 0
while len(t) != 0 and idx < n:
    if d[idx] == t[0]:
        t.pop(0)
    elif d[idx] > t[0]:
        print("NO")
        exit()
    idx += 1
print("YES") if len(t) == 0 else print("NO")

### FIXED CODE ###

import collections
n = int(input())
d_ = [int(i) for i in input().split()]
m = int(input())
t_ = [int(i) for i in input().split()]
d = collections.Counter(d_)
t = collections.Counter(t_)
for ti in t_:
    if d[ti] == 0:
        print("NO")
        exit()
    else:
        d[ti] -= 1
print("YES")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
h = [int(x) for x in input().split()]

ans = 0

def solve(l, r):
    global ans
    if l >= r:
        return
    if 0 not in h[l:r]:
        minh = min(h[l:r])
        ans += minh
        for i in range(l, r):
            h[i] -= minh
        solve(l, r)
    else:
        for i in range(l, r):
            if h[i] == 0:
                solve(l, i)
                solve(i + 1, r)
solve(0, n)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
h = [int(x) for x in input().split()]
h = np.array(h,np.int64)
ans = 0
def split_(A):
    global ans
    if np.count_nonzero(A != 0) == 0:
        return
    else:
        minA = A.min()
        A -= minA
        ans += minA
        for i in range(len(A)):
            if A[i] == 0:
                split_(A[:i])
                split_(A[i+1:])
                break
split_(h)
print(ans)
### BUGGY CODE ###

num = int(input())

def function(a,b):
    return (max(len(str(a)),len(str(b))))

d = len(str(num))

for i in range(1,num+1):
    if num % i == 0:
        b = int(num // i)
        c = function(i,b)
        if d >= c:
            d = c
        else:
            print(d)
            exit()
print(d)

### FIXED CODE ###

num = int(input())

digits = len(str(num))

ans = digits

for i in range(1,10 ** (digits // 2 + 1)):
    if num % i == 0:
        target = max(len(str(i)), len(str(num//i)))
        if ans >= target:
            ans = target
        else:
            print(ans)
            exit()
print(ans)
### BUGGY CODE ###

#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[0]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[0][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0][:]
        cost = previous[1]
        for x in previous[0]:
            A = x[0] + medichine[n][0]
            B = x[1] + medichine[n][1]
            C = x[2] + medichine[n][2]
            if C < cost:
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

K, S = [int(i) for i in input().split()]
AA = [1 for X in range(K+1) for Y in range(K+1) for Z in range(K+1) if X+Y+Z==S]
print(len(AA))

### FIXED CODE ###

K, S =[int(i) for i in input().split()]
C = 0
for X in range(K+1):
    for Y in range(K+1):
        if X+Y <= S <= X+Y+K:
            C += 1
print(C)
### BUGGY CODE ###

R,G,B,N = map(int, input().split())

maxr=N//R
maxg=N//G
maxb=N//B

ans=0
flg=0
for i in range(maxr,-1,-1):
  for j in range(maxg,-1,-1):
    for k in range(maxb,-1,-1):
      if R*i+G*j+B*k==N:
        ans+=1
        break
print(ans)

### FIXED CODE ###

R,G,B,N = map(int, input().split())

maxr=N//R
maxg=N//G

ans=0
for r in range(maxr,-1,-1):
  for g in range(maxg,-1,-1):
    if N-(r*R+g*G)>=0:
      if (N-(r*R+g*G))%B==0:
        ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x <= y:
          return x
        else:
          return y

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res, seg[p])
            if q&1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 10**9+1

    # num: n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num

    init(A)

    ans = 10**18
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += min(query(i-k, i-k//2), query(i-k//2, i+1))
            else:
                temp1 = min(query(0, i//2), query(i//2, i+1))
                temp2 = min(query(n-(k-i), n-(k-i)//2), query(n-(k-i)//2, n))
                if temp1 <= temp2:
                    t += temp1
                else:
                    t += temp2
        if t <= ans:
            ans = t
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(50)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


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

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

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
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])
### BUGGY CODE ###

h,w,K=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())

ans=float("inf")
for i in range(2**(h-1)):
    cut=[]
    linecount=0
    for j in range(h-1):
        if (i>>j)%2==1:
            cut.append(j)
    counter=[0]*(len(cut)+1)
    for j in range(w):
        ncounter=[0]*(len(cut)+1)
        area=0
        flag=False
        for k in range(h):
            ncounter[area]+=(s[k][j]=="1")
            if counter[area]+ncounter[area]>K:
                flag=True
            if k in cut:
                area+=1
        if flag:
            counter=ncounter[:]
            linecount+=1
        else:
            for l in range(len(cut)+1):
                counter[l]+=ncounter[l]
    ans=min(ans,linecount+len(cut))
print(ans)
        





### FIXED CODE ###

h,w,K=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())

ans=float("inf")
for i in range(2**(h-1)):
    cut=[]
    linecount=0
    for j in range(h-1):
        if (i>>j)%2==1:
            cut.append(j)
    counter=[0]*(len(cut)+1)
    for j in range(w):
        ncounter=[0]*(len(cut)+1)
        area=0
        flag=False
        for k in range(h):
            ncounter[area]+=int(s[k][j])
            if counter[area]+ncounter[area]>K:
                if ncounter[area]>K:
                    linecount=float("inf")
                flag=True
            if k in cut:
                area+=1
        if flag:
            counter=ncounter[:]
            linecount+=1
        else:
            for l in range(len(cut)+1):
                counter[l]+=ncounter[l]
    ans=min(ans,linecount+len(cut))
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k + 1):
    for j in range(k + 1):
        for k in range(k + 1):
            if i + j + k == s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k + 1):
    for j in range(k + 1):
        if 0 <= s - i - j <= k:
            ans += 1
print(ans)