做法来自 @farmerjiang，已经过本人授权。
给一种证明部分完全与反悔无关的做法，会比反悔思路简单很多。
解题思路
考虑如下做法：
- 添加 n 张限制为 a_i，优惠为 a_i-b_i 的虚空优惠券。
- 然后仅考虑 n 件商品的原价以及这 n+m 张优惠券，用它们进行朴素贪心 ^\dagger，得到的答案即为本题的答案。
我们考虑为什么这么做是对的：容易发现这么做唯一的问题在于可能有一个原价不为 $a_i$ 的商品 $a_j$ 使用了 $a_i$ 产生的虚空优惠券，根据贪心这个时候 $a_i$ 会使用另一张优惠券减 $x$ 元，记这一张优惠券的限制为 $lim$。
可以发现 $a_j$ 会抢走 $a_i$ 的虚空优惠券的一个必要条件是 $a_j\geq a_i$，又有 $lim\leq a_i \leq a_j$，故此时交换 $a_i$ 与 $a_j$ 的优惠券可以使得 $a_i$ 使用自己产生的虚空优惠券，即使用原先的 $b_i$ 折扣，并且不会产生任何额外代价。
故经过若干次交换可以使得每一个商品使用原先给出的优惠券以及自己的虚空优惠券，并且在此限制条件下不会产生比朴素贪心更高的代价，故正确性得证。
时间复杂度 $O(n\log (n+m))$。