[AdditionalFile5233.zip](file://AdditionalFile5233.zip?type=additional_file)

#5233. 「UOI 2021 Stage 4 Day2」敌人与军刀

标签: 传统 | 时间限制: 5000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2021 Stage 4 Day2 T4. Вороги та шаблі

科扎克·武斯来到塞奇，拜访了一位在工坊中开始打造军刀的熟人。这位熟人已经打造了 $n$ 把军刀，其中第 $i$ 把军刀有两个参数——长度和锋利度，分别记为 $a_i$ 和 $b_i$，并且第 $i$ 把军刀的价格为 $cost_i$ 卡尔波瓦涅茨（货币单位）。

最近，塞奇出现了 $m$ 个敌人。首领为每个敌人设定了赏金——抓住第 $j$ 个敌人可以获得 $profit_j$ 卡尔波瓦涅茨的赏金。但不同敌人的护甲参数也不同——护甲的厚度和强度分别记为 $c_j$ 和 $d_j$。

要抓住一个敌人，必须刺穿他的护甲。为此，需要一把军刀，其长度不小于护甲的厚度，锋利度不小于护甲的强度。形式上，用第 $i$ 把军刀可以抓住第 $j$ 个敌人，当且仅当满足两个条件：$a_i \geq c_j$ 且 $b_i \geq d_j$。

科扎克·武斯想知道他最多能赚取多少卡尔波瓦涅茨，以便决定是否从事这种危险的工作，并请求你的帮助。

请注意，在塞奇可以借贷卡尔波瓦涅茨，也就是说，科扎克·武斯在某些时刻可能拥有负数的卡尔波瓦涅茨。此外，科扎克·武斯可以使用一把军刀来抓住多个敌人。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 10^{6})$，分别表示军刀和敌人的数量。

接下来的 $n$ 行，每行包含三个整数 $a_i, b_i, cost_i$ $(0 \leq a_i, b_i, cost_i \leq 10^{9})$，分别表示第 $i$ 把军刀的长度、锋利度和价格。

接下来的 $m$ 行，每行包含三个整数 $c_j, d_j, profit_j$ $(0 \leq c_j, d_j, profit_j \leq 10^{9})$，分别表示第 $j$ 个敌人的护甲厚度、强度以及抓获他的赏金。

输出格式

输出一个整数，表示科扎克·武斯能赚取的最大卡尔波瓦涅茨数量。

样例

输入

2 2
2 4 10
4 5 15
1 3 50
3 1 100

输出

135

数据范围与提示

详细子任务附加限制及分值如下表所示：