No.042 C

おやつは金額の降順にソートしておく.

$i$ 番目のおやつまで見たときに金額 $j$ で取得できる最大満足度を $C(i, j)$ とすると,

$$C(i, j) = \max(C(i-1, j), C(i-1, j-a_i) + b_i)$$

となる. これを DP で更新する.

金額は $i$ 番目のおやつまでなら $P+a_i$ 円まで使えるので,

$$\max_{1 \leq i \leq N}(\max_{1 \leq j \leq P+a_i} C(i, j))$$

を求めればいい.