No.286

BitDP を使う.

商品の集合 $A$ を買ったときの定価の合計を $S(A)$, 払った金額の合計の最小値を $P(A)$ とすると,

$$S(A) = S(A \setminus a) + M_a \ (\exists a \in A) \\ P(A) = \min_{a \in A}(P(A \setminus a) + \max(M_a - S(A \setminus a) \ mod \ 1000, 0))$$

となる.