4057. 买东西题

【题目背景】

【题目描述】

你要买 n 个物品，第 i 个物品原价 ai 元，折扣价 bi 元（保证 bi≤ai）。

你还有 m 个满减优惠券，第 j 个优惠券形如原价满 wj 减 vj（保证vj≤wj）。

对于第 i 个物品，你可以选择以下三种购买方式之一：使用原价 ai 购买。使用折扣价 bi 购买。选择一个未使用过的优惠券 j，要求满足 ai≥wj，使用优惠券 j，以 ai−vj 的价格购买。注意每个优惠券 j 只能被最多一个 i 使用。求购买所有物品最少用钱。

【输入格式】

第一行，两个正整数 n,m，表示物品数量和优惠券数量。

接下来 n 行，每行两个正整数 ai,bi，表示第 i 个物品的原价和折扣价。

接下来 m 行，每行两个正整数 wj,vj，表示第 j 个优惠券是满 wj 减 vj 的。

【输出格式】

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

【样例1输入】

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

【样例1输出】

12

【样例1说明】

因为满足w2≤a1 即 7≤7，所以可以使用原价和第 2 个优惠券购买第 1 个物品，花费 7−4=3 元。

因为满足 w4≤a2 即 3≤4，所以可以使用原价和第 4 个优惠券购买第 2 个物品，花费 4−2=2 元。

使用折扣价购买第 3 个物品，花费 2 元。

使用原价和第 3 个优惠券购买第 4 个物品，花费 6−4=2 元。

使用折扣价购买第 5 个物品，花费 3 元。

共 3+2+2+2+3=12 元。可以证明这是最少用钱方案。

【样例2输入】

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

【样例2输出】

12

【样例2说明】

使用原价和第 22 个优惠券购买第 11 个物品。

使用折扣价购买第 22 个物品。

使用原价和第 11 个优惠券购买第 33 个物品。

共 0+1+0=10+1+0=1 元。

【数据规模与约定】

对于所有测试数据，保证：1≤n,m≤10^6，1 1≤ai,bi,wj,vj≤10^9，bi≤ai，vj≤wj。

【来源】

在此键入。