【MX-S5-T2】买东西题

原题链接：<https://oier.team/problems/S5B>。 --- **此题题意与关联的现实生活情景略有不同，请认真阅读题目描述。**

你要买 $n$ 个物品，第 $i$ 个物品原价 $a_i$ 元，折扣价 $b_i$ 元（保证 $b_i \le a_i$）。 你还有 $m$ 个满减优惠券，第 $j$ 个优惠券形如**原价**满 $w_j$ 减 $v_j$（保证 $v_j \le w_j$）。 对于第 $i$ 个物品，你可以选择以下三种购买方式之一： 1. 使用**原价** $a_i$ 购买。 2. 使用**折扣价** $b_i$ 购买。 3. 选择**一个未使用过的优惠券** $j$，要求满足 $a_i \ge w_j$，使用优惠券 $j$，以 $a_i - v_j$ 的价格购买。注意每个优惠券 $j$ 只能被**最多一个** $i$ 使用。 求购买所有物品最少用钱。

第一行，两个正整数 $n,m$，表示物品数量和优惠券数量。 接下来 $n$ 行，每行两个正整数 $a_i,b_i$，表示第 $i$ 个物品的原价和折扣价。 接下来 $m$ 行，每行两个正整数 $w_j,v_j$，表示第 $j$ 个优惠券是满 $w_j$ 减 $v_j$ 的。

仅一行，一个整数，表示最少用钱。

5 4
7 5
4 2
5 2
6 4
6 3
5 1
7 4
5 4
3 2

12

3 4
3 2
5 1
5 5
5 5
3 3
4 2
2 1

1

**【样例解释 #1】** 因为满足 $w_2\le a_1$ 即 $7\le 7$，所以可以使用原价和第 $2$ 个优惠券购买第 $1$ 个物品，花费 $7-4=3$ 元。 因为满足 $w_4\le a_2$ 即 $3\le 4$，所以可以使用原价和第 $4$ 个优惠券购买第 $2$ 个物品，花费 $4-2=2$ 元。 使用折扣价购买第 $3$ 个物品，花费 $2$ 元。 使用原价和第 $3$ 个优惠券购买第 $4$ 个物品，花费 $6-4=2$ 元。 使用折扣价购买第 $5$ 个物品，花费 $3$ 元。 共 $3+2+2+2+3=12$ 元。可以证明这是最少用钱方案。 **【样例解释 #2】** 使用原价和第 $2$ 个优惠券购买第 $1$ 个物品。 使用折扣价购买第 $2$ 个物品。 使用原价和第 $1$ 个优惠券购买第 $3$ 个物品。 共 $0+1+0=1$ 元。 **【样例 #3】** 见附件中的 `buy/buy3.in` 与 `buy/buy3.ans`。 该组样例满足测试点 $3$ 的约束条件。 **【样例 #4】** 见附件中的 `buy/buy4.in` 与 `buy/buy4.ans`。 该组样例满足测试点 $5\sim 6$ 的约束条件。 **【样例 #5】** 见附件中的 `buy/buy5.in` 与 `buy/buy5.ans`。 该组样例满足测试点 $8$ 的约束条件。 **【样例 #6】** 见附件中的 `buy/buy6.in` 与 `buy/buy6.ans`。 该组样例满足测试点 $9\sim 10$ 的约束条件。 **【数据范围】** 对于所有测试数据，保证：$1 \le n,m \le 10^6$，$1 \le a_i,b_i,w_j,v_j \le 10^9$，$b_i\le a_i$，$v_j\le w_j$。 | 测试点编号 | $n\le$ | $m\le$ | $a_i,w_j\le$ | 特殊性质 | | :--------: | :-------: | :-------: | :-------: | :------: | | $1$ | $10$ | $10$ | $10$ | 无 | | $2$ | $10^5$ | $10^5$ | $10^4$ | $a_i=b_i$ | | $3$ | $10^5$ | $10^5$ | $10^9$ | $a_i=b_i$ | | $4$ | $10^5$ | $10^5$ | $10^4$ | $\max_j w_j\le\min_i a_i$ | | $5\sim 6$ | $10^5$ | $10^5$ | $10^9$ | $\max_j w_j\le\min_i a_i$ | | $7$ | $10^3$ | $10^3$ | $10^6$ | 无 | | $8$ | $10^3$ | $10^3$ | $10^9$ | 无 | | $9\sim 10$ | $10^6$ | $10^6$ | $10^9$ | 无 |