题意

有 500,100,50,10,5,1 这些面额的纸币，有 $X$ 块钱，使用最少的纸币数表示的。

然后有一些物品，每种只有一个，有费用。每次你可以选择一些没买过的买，付一定的钱，用最小的纸币数会找你钱。

要求最大化最后 1 元纸币的数量。

$n\leq10^5,X\leq10^{14}$ 。

口胡

有性质是一次只会买一个。

然后有 $\mathcal{O}(n^2)$ 的背包做法，考虑优化。注意到贡献其实只有 0 到 4。就不用价格做状态，用价值做状态。

按费用从小到大选。贪心改变贡献选的数量。

那设置一个波动 $B$ ，如果贪心选的数量是 $x$ ，就只需要 DP $[x-B, x+B]$ 的结果。复杂度 $\mathcal{O}(n+B^2)$ 。