P11349 [NOISG 2024 Finals] Problem Setter

Stuart 是一名热衷于编程比赛的题目设计者，他为多个比赛设定了许多问题。他希望将自己的一些问题提交到编程比赛中，以获得更多的荣誉。

Stuart 可以将题目提交到 $c$ 个比赛中。如果将问题提交到第 $i$ 个比赛，他的满意度会增加 $s_i$。但由于比赛的结构和其他题目设计者的竞争，第 $i$ 个比赛只会接受质量至少为 $m_i$ 的题目。每个比赛可以接受多个问题，每个问题都会增加 $s_i$ 的满意度。 Stuart 总共设计了 $p$ 道问题，他认为第 $j$ 道问题的质量是 $q_j$。但由于问题准备过程的难度，提交第 $j$ 道问题到任何比赛会使他的满意度减少 $d_j$。显然，每个问题最多只能提交到一个比赛，或者可以选择不提交。 请帮 Stuart 找到一个最优的提交方案，以使他的满意度最大化。如果所有提交方案都会导致负满意度，他可以选择不提交任何问题，最终满意度为 $0$。

- 第一行包含两个整数 $c$ 和 $p$，分别表示比赛数量和问题数量。 - 接下来的 $c$ 行中，第 $i$ 行包含两个整数 $m_i$ 和 $s_i$，表示第 $i$ 个比赛的最低问题质量和增加的满意度。 - 接下来的 $p$ 行中，第 $j$ 行包含两个整数 $q_j$ 和 $d_j$，表示第 $j$ 道问题的质量和提交所带来的满意度损失。

- 输出一个整数，表示 Stuart 可以获得的最大满意度。如果他选择不提交任何问题，输出 $0$。

【样例解释】 对于样例 #1： - 比赛 $1$ 的最低质量要求为 $2$，问题 $1$ 满足条件，提交后增加 $5 - 2 = 3$ 的满意度。 - 比赛 $1$ 的最低质量要求为 $2$，问题 $2$ 满足条件，提交后增加 $5 - 4 = 1$ 的满意度。 - 最终满意度为 $3 + 1 = 4$。 - 问题 $3$ 和其他比赛没有提交。 对于样例 #2： - 根据提交方案，最优满意度为 $11$。 对于样例 #3： - 最优方案使满意度为 $2$。 【数据范围】 - $1 \leq c, p \leq 200,000$ - $0 \leq m_i, s_i, q_j, d_j \leq 1,000,000$ | 子任务编号 | 分值 | 限制条件 | |:---:|:---:|:---:| | $0$ | $0$ | 样例测试用例 | | $1$ | $18$ | $1 \leq c \leq 1,000, p = 1$ | | $2$ | $16$ | $1 \leq c, p \leq 1,000$ | | $3$ | $26$ | $d_j = 0$ | | $4$ | $40$ | 无额外限制 |