Money for Nothing
题目描述
在这道题种你需要解决一个全世界人类从存在起就在面临的最深刻的问题--如何发大财。你是一名零件交易市场的
中介。你的工作是从零件生产公司那里买到零件,然后把它们卖给零件消费公司。每个零件消费公司在截止日期前
每天都会对一个零件有一个开放式的需求,以及它愿意买下零件的价格。另一方面,每个零件生产公司在开始日期及
以后都可以销售零件,以及它销售零件的价格。基于公平竞争法,你只能与一家生产公司、一家消费公司签订合同。
你可以在生产公司开始销售后每天从生产公司买一个零件,当然这也要在消费公司结束需求之前。在这些天里,每天
你可以从买卖差价中获取利润。你的任务是选择能使你利益最大化的生产公司与消费公司。
输入格式
第一行包含两个整数m和n(1≤m,n≤500 000),分别表示市场里生产公司与消费公司的数量。
接下来m行,第i行包含两个整数pi和di(1≤pi,di≤10^9),表示第i个生产者卖一个零件的价格和第一个零件开始卖的日期。
接下来n行,第j行包含两个整数qj和ej(1≤qj,ej≤ 10^9)
表示第j个消费者愿意买一个零件的价格和它可以接收最后一个零件的日期的下一天。
输出格式
输出你最多能赚到多少钱。如果你没办法通过签合同获利,输出0。
样例1
2 2
1 3
2 1
3 5
7 2
样例2
1 2
10 10
9 11
11 9
样例1
5
样例2
0