Description

在这个问题中，你将解决自古以来人类面临的最深刻的挑战之一——如何赚很多钱。

你是小工具市场中的一个中间商。你的工作是从小工具生产公司购买小工具，然后将其出售给小工具消费公司。每个小工具消费公司每天都有一个开放的请求，直到某个结束日期，并且有一个愿意购买小工具的价格。另一方面，每个小工具生产公司都有一个开始交付小工具的日期和一个交付每个小工具的价格。

由于公平竞争法，你只能与一个生产公司和一个消费公司签订合同。你将从生产公司购买小工具，每天一个，从它可以开始交付的那天开始，到消费公司指定的日期结束。在这些天中，你赚取生产商的售价与消费者的购买价之间的差额。

你的目标是选择能够最大化利润的消费公司和生产公司。

Input Format

输入的第一行包含两个整数 $m$ 和 $n$ $(1 \le m , n \le 500 000)$，分别表示市场中的生产公司和消费公司的数量。接下来是 $m$ 行，第 $i$ 行包含两个整数 $p_{i}$ 和 $d_{i}$ $(1 \le p_{i}, d_{i} \le 10^{9})$，表示第 $i$ 个生产公司出售一个小工具的价格（美元）和该公司第一个小工具可用的日期。然后是 $n$ 行，第 $j$ 行包含两个整数 $q_{j}$ 和 $e_{j}$ $(1 \le q_{j}, e_{j} \le 10^{9})$，表示第 $j$ 个消费公司愿意购买小工具的价格（美元）和该公司最后一个小工具必须交付后的第二天。

Output Format

请输出你能赚取的最大总美元数。如果没有办法签订合同以获得任何利润，则请输出 0。

2 2
1 3
2 1
3 5
7 2

5

1 2
10 10
9 11
11 9

0

Hint

时间限制：5 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。