\(1\) 回の会計で \(1\) つの商品を購入するのが最適です。また持っている \(1\) 円玉は支払わない方が良いです。よって \(A\) 円の商品は価値 \(5-A \% 5\)、重み \(A+5-A \% 5\) として、容量が \(X - X \% 5\) のナップザック問題に帰着できます。(値段が \(5\) の倍数の商品は無視します)

この問題では価値が \(1〜4\) と小さいことを利用して高速に解きます。各価値ごとに商品を重みの昇順にソートします。ここで各価値ごとに使う価値の合計を \(12\) で割った余りを決め打ちます。各価値ごとに下から決め打った余りの分だけ使うと、残りの商品は下から順に価値 \(12\) ごとにまとめることができます。後は重さの小さい順に容量いっぱいまで価値 \(12\) のまとまりを詰めていけばよいです。

価値 \(1〜4\) それぞれ \(12\) で割った余りを決め打って \(\frac{12}{1} × \frac{12}{2} × \frac{12}{3} × \frac{12}{4} \) 通りを全探索すると \(O(NlogN)\) で解くことができます。