题目描述

译自 NOISG 2024 Final T1. Problem Setter

过去几年，斯图尔特出了许多题目。现在他正在考虑是否将这些题目提交到编程竞赛（包括本次竞赛！），以获得由国内甚至全球顶尖编程选手解决这些题目的荣誉。

有 $c$ 个竞赛可供斯图尔特提交题目。向第 $i$ 个竞赛提交任意题目将增加他的满意度 $s[i]$。然而，由于竞赛的结构以及其他出题者的竞争，斯图尔特认为第 $i$ 个竞赛只会接受品质至少为 $m[i]$ 的题目。注意，斯图尔特可以向任意竞赛提交任意数量的题目，每提交一道题目将增加满意度 $s[i]$。

斯图尔特创作了 $p$ 道题目。他认为第 $j$ 道题目的品质为 $q[j]$。然而，由于题目准备过程的难度，向任意竞赛提交第 $j$ 道题目将减少他的满意度 $d[j]$。显然，每道题目最多只能提交到一个竞赛，或者如果他选择不提交，则不提交到任何竞赛。

请计算斯图尔特通过向各竞赛提交合适的题目所能获得的最大满意度。注意，如果所有提交方式都会导致负满意度，斯图尔特可以选择不提交任何题目，最终满意度为 $0$。

输入格式

程序需从标准输入读取数据。

输入的第一行包含两个空格分隔的整数 $c$ 和 $p$，分别表示竞赛数量和题目数量。

接下来的 $c$ 行，第 $i$ $(1 \leq i \leq c)$ 行包含两个空格分隔的整数 $m[i]$ 和 $s[i]$，分别表示该竞赛的最低题目品质和提交题目获得的满意度。

接下来的 $p$ 行，第 $j$ $(1 \leq j \leq p)$ 行包含两个空格分隔的整数 $q[j]$ 和 $d[j]$，分别表示该题目的品质和提交该题目导致的满意度损失。

输出格式

程序需向标准输出输出结果。

输出包含 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个查询的答案。

3 3
2 5
1 1
8 3
3 2
9 4
1 3

4

有 $3$ 个竞赛和 $3$ 道题目。

斯图尔特可以将品质为 $3$ 的题目 $1$ 提交到竞赛 $1$，因为其品质高于竞赛的最低品质 $2$，获得 $5-2=3$ 的满意度。他可以将品质为 $9$ 的题目 $2$ 提交到竞赛 $1$，获得 $5-4=1$ 的满意度。总计获得 $4$ 的满意度。

注意，他选择不提交题目 $3$，也不向竞赛 $2$ 和 $3$ 提交任何题目。

这个样例满足子任务 $2,4$ 的限制。

3 4
2 3
1 1
8 4
2 0
7 0
1 0
8 0

11

有 $3$ 个竞赛和 $4$ 道题目。

斯图尔特可以将题目 $1$ 和 $2$ 提交到竞赛 $1$，题目 $3$ 提交到竞赛 $2$，题目 $4$ 提交到竞赛 $3$。总计获得 $3 \times 2 + 1 + 4 = 11$ 的满意度。

这个样例满足子任务 $2,3,4$ 的限制。

5 1
3 4
1 2
5 6
2 8
4 0
3 6

2

有 $5$ 个竞赛和 $1$ 道题目。

斯图尔特将唯一的题目提交到竞赛 $4$，获得 $8-6=2$ 的满意度。

这个样例满足子任务 $1,2,4$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq c, p \leq 200000$
• $0 \leq m[i], s[i], q[j], d[j] \leq 1000000$，对于所有 $1 \leq i \leq c$，$1 \leq j \leq p$

详细子任务附加限制及分值如下表所示：