该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

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

题目描述

你要买 $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

样例 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$ 元。可以证明这是最少用钱方案。

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

1

样例 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$。

下发文件

通过点击此链接下载下发文件。