T2 购物

第一档是给一些奇奇怪怪的暴力枚举的分。

第二档可以用状压 DP 决定哪些物品至少买一个，在这里我们发现一个基本事实：我们至多让一种物品选很多次。

证：因为如果两个物品同时选多次，那么一定是两个都被选过一次，那么用 $b_i$ 更大的去替换另一个一定不劣。

对于第三档，很显然就是所有物品先都买一遍，然后找到最大的 $b$ 一直买就行。

对于整道题目，考虑前面那个结论，我们可以直接枚举被选多次的那个物品 $k$，那么考虑其它物品，如果它们被选一次，那么一定是 $a_i>b_k$，这样做是 $O(n^2)$ 的，考虑按 $a_i$ 进行排序，二分找到第一个比当前枚举位置小的，那么前面的全部选择，用前缀和简单维护就好了。