No.385

まずは何円使えば最大いくつのカップ麺を買えるかを DP で計算する.

$i$ 番目のカップ麺まで見たときに $j$ 円で購入できる最大のカップ麺の数を $A(i, j)$ とすると,

$$A(i, j) = \max(A(i-1, j), A(i, j-C_i) + 1)$$

となるので, これを順番に更新する.

次に, $M - k$ が素数になる数の最大カップ麺購入数 $A(N, k)$ をすべて足し, 最後に $A(N, k)$ の最大値を加える.