题目描述

小爱是一名电脑供应商，她有 $n$ 台电脑，第 $i$ 台电脑的计算能力为 $a_i$，如果这台电脑卖出了，她需要支付进货价 $c_i$ 元（如果没有卖出，就不需要支付）。这批电脑是小爱精心挑选过的，保证它们之间的性价比是合理的，即性能高的电脑进货价不会低于性能低的进货价。

小爱接到了 $m$ 张订单，其中第 $j$ 张订单要求一台运算能力不低于 $q_j$ 的电脑，出价是 $b_j$ 元。如果小爱觉得一些订单的报价不合理，她可以拒绝交易。请帮忙计划一下，小爱应该接受哪些订单，才能将利润最大化。

输入格式

• 第一行：两个整数 $n$ 与 $m$
• 接下来的 $n$ 行，在其中的第 $i$ 行，有两个整数表示 $a_i$ 与 $c_i$
• 接下来的 $m$ 行，在其中的第 $j$ 行，有两个整数表示 $q_j$ 与 $b_j$
• 保证 $a_1\leq a_2\leq \dots \leq a_n$
• 保证 $c_1\leq c_2\leq \dots \leq c_n$

输出格式

单个整数：表示小爱盈利的最大值。

3 2 
20 1000 
20 1500 
30 4000 
10 2000 
30 7000

4000

数据范围

• 对于 $30\%$ 的数据，$1\leq n, m\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n,m\leq 1000$；
• 对于 $100\%$ 的数据，$1\leq n, m\leq 300,000$；
• $1\leq a_i,q_i\leq 300,000$；
• $1\leq c_i,b_i\leq 1,000,000$。