#P51863. 「ICPC World Finals 2017」不劳而获的钱财 Money for Nothing

「ICPC World Finals 2017」不劳而获的钱财 Money for Nothing

题目描述

在这道题种你需要解决一个全世界人类从存在起就在面临的最深刻的问题——如何发大财。

你是一名零件交易市场的中介。你的工作是从零件生产公司那里买到零件,然后把它们卖给零件消费公司。每个零件消费公司在截止日期前每天都会对一个零件有一个开放式的需求,以及它愿意买下零件的价格。另一方面,每个零件生产公司在开始日期及以后都可以销售零件,以及它销售零件的价格。

基于公平竞争法,你只能与一家生产公司、一家消费公司签订合同。你可以在生产公司开始销售后每天从生产公司买一个零件,当然这也要在消费公司结束需求之前。在这些天里,每天你可以从买卖差价中获取利润。

你的任务是选择能使你利益最大化的生产公司与消费公司。

输入格式

第一行包含两个整数 mmnn (1m,n500 000)(1 \leq m, n \leq 500\ 000),分别表示市场里生产公司与消费公司的数量。

接下来 mm 行,第 ii 行包含两个整数 pip_idid_i (1pi,di109)(1 \leq p_i, d_i \leq 10^9),表示第 ii 个生产者卖一个零件的价格和第一个零件开始卖的日期。

接下来 nn 行,第 jj 行包含两个整数 qjq_jeje_j (1qj,ej109)(1 \leq q_j, e_j \leq 10^9),表示第 jj 个消费者愿意买一个零件的价格和它可以接收最后一个零件的日期的下一天。

输出格式

输出你最多能赚到多少钱。如果你没办法通过签合同获利,输出 0

样例 1

2 2
1 3
2 1
3 5
7 2
5
1 2
10 10
9 11
11 9
0