题目描述

哥萨克 Vus 来到营地拜访一位朋友，这位朋友在自己的工坊里开始锻造军刀。朋友已经锻造了 $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$。

哥萨克 Vus 想知道他最多能赚取多少卢布，以便决定是否值得从事如此危险的工作，并请你帮忙。

请注意，营地里可以赊账，因此哥萨克 Vus 在某些时刻可能拥有负数的卢布。此外，哥萨克 Vus 可以用同一把军刀抓住多个敌人。

输入格式

第一行包含两个整数 $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$ 个敌人的护甲厚度、强度和悬赏金额。

输出格式

输出一个整数——哥萨克 Vus 能赚取的最大卢布数。

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

135

提示

评分标准

• （13 分）：对于任意两个不同的敌人 $(i,j)$，要么 $c_i > c_j$，要么 $d_i > d_j$，即不存在一个敌人其护甲的两个参数均不劣于另一个敌人；$n, m \leq 5\,000$；
• （10 分）：对于任意两个不同的敌人 $(i,j)$，要么 $c_i > c_j$，要么 $d_i > d_j$，即不存在一个敌人其护甲的两个参数均不劣于另一个敌人；$n, m \leq 10^5$；
• （13 分）：对于任意两把不同的军刀 $(i,j)$，要么 $a_i > a_j$，要么 $b_i > b_j$，即不存在一把军刀其攻击的两个参数均不劣于另一把军刀；$n, m \leq 5\,000$；
• （10 分）：对于任意两把不同的军刀 $(i,j)$，要么 $a_i > a_j$，要么 $b_i > b_j$，即不存在一把军刀其攻击的两个参数均不劣于另一把军刀；$n, m \leq 10^5$；
• （14 分）：$n, m \leq 5000$；
• （23 分）：$n, m \leq 10^5$；
• （17 分）：无额外限制。