AtCoder AGC044 A問題 9testfile中2WAとなってしまう原因が分かりません

前提・実現したいこと

AtCoder AGC044 A問題に関する質問です。
下記のプログラムを作成しましたが、WAとなってしまいました。
どこが原因となっているかをお聞きしたいです。
9testfile中2WAとなっているようで、問題文中のtestfileに関しては正常に作動しました。

発生している問題・エラーメッセージ

テストケース005.txtと007.txtでエラー

#コンテストですのでエラーメッセージは確認出来ませんでした
ソースコード
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
t = int(input())
l = [list(map(int, input().split())) for i in range(t)]

 
for i in range(t):
    N = l[i][0]
    A = l[i][1]
    B = l[i][2]
    C = l[i][3]
    D = l[i][4]
    @lru_cache(maxsize=10**18) #再帰で呼び出すのでメモ化
    def min_coin(n): #再帰を使って到達する数を減らしていく
        if(n == 0):
            return 0
        elif(n == 1):
            return D #特殊な0,1を先に省く
        else:
            if(n%2 == 0):
                a = min_coin(n/2)
            else:
                a = min(min_coin(n//2)+D,min_coin(n//2+1)+D) #上下両方の偶数からの個数を比較する
            if(n%3 == 0):
                b = min_coin(n/3)
            elif(n%3 == 1):
                b = min(min_coin(n//3)+D,min_coin(n//3+1)+D*2)
            else:
                b = min(min_coin(n//3)+D*2,min_coin(n//3+1)+D)
            if(n%5 == 0):
                c = min_coin(n/5)
            else:
                re = n%5
                c = min(min_coin(n//5)+D*re,min_coin(n//5+1)+D*(5-re))
            return min(a+A,b+B,c+C,D*n)   
    print(int(min_coin(N)))

```python



### 試したこと

問題文中のテストファイルを試しましたがそちらでは想定解となりました
#####入力
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

#####出力
20
19
26
3821859835
23441258666

AtCoderにて提出しましたが、WAとなりました。
実行時間には特に問題がありませんでした。
ただ、関係があるかは分かりませんが、400ms以下で終了したものは全てACであるのに対して、WAとなったファイルでは467ms,597msとなりました、
再帰回数の上限を10000→100000→1000000と変えましたが、変化はありませんでした。

### 補足情報（FW/ツールのバージョンなど）