お金を払って買う商品については \(B_i\) が大きいものから買うのが最適なので, \(B_i\) で降順にソートしておく.

あとはどのカードをキャンペーンでもらうかを考える.

\(i\) 番目の商品まで見たときに \(j\) 個の商品をキャンペーンでもらっている場合の金額を \(C(i, j)\) とする.

このとき, \(i+1\) 番目の商品をお金を払って買う場合は \(i-j\) 個の商品をすでにお金を払って買っているので \(i+1\) 番目の商品は \(A_{i+1} + (i-j)B_{i+1}\) 円となる.

よって,

\[C(i+1, j) = \min \{ C(i, j-1), C(i, j) + A_{i+1} + (i-j)B_{i+1} \}\]

となる.