题目背景

原题链接：https://oier.team/problems/90。

---

此题题意与关联的现实生活情景略有不同，请认真阅读题目描述。

题目描述

你要买 $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$			无
$2$	$10^5$		$10^4$	$a_i=b_i$
$3$			$10^9$
$4$			$10^4$	$\max_j w_j\le\min_i a_i$
$5\sim 6$			$10^9$
$7$	$10^3$		$10^6$	无
$8$			$10^9$
$9\sim 10$	$10^6$