题目描述

你正在一家出售 $M$ 件商品的商店购物。商店的布局可以建模为一个二维平面，其中第 $i$ 件商品位于点 $(x_i, y_i)$，价格为 $p_i$。

商店提供 $N$ 种购物优惠。第 $i$ 种购物优惠由点 $(a_i, b_i)$ 指定，花费 $c_i$ 的代价，你可以选择以下四个区域之一，获得该区域内所有商品各一件：

• 满足 $x \leq a_i$ 且 $y \leq b_i$ 的点 $(x, y)$ 所在区域
• 满足 $x \leq a_i$ 且 $y \geq b_i$ 的点 $(x, y)$ 所在区域
• 满足 $x \geq a_i$ 且 $y \leq b_i$ 的点 $(x, y)$ 所在区域
• 满足 $x \geq a_i$ 且 $y \geq b_i$ 的点 $(x, y)$ 所在区域

每种购物优惠最多只能使用一次。商品也可以单独购买，只需支付其对应的价格 $p_i$。

你需要获取商店中的每件商品至少一件。求达成该目标所需支付的最小总成本。

输入格式

第一行输入包含两个以空格分隔的整数 $N$ 和 $M$。

接下来 $N$ 行每行包含三个以空格分隔的整数 $a_i$、$b_i$ 和 $c_i$（$-10^9 \leq a_i, b_i \leq 10^9$，$1 \leq c_i \leq 10^9$）。

随后 $M$ 行每行包含三个以空格分隔的整数 $x_i$、$y_i$ 和 $p_i$（$-10^9 \leq x_i, y_i \leq 10^9$，$1 \leq p_i \leq 10^9$）。

输出格式

输出一行，表示获取所有商品至少一件所需的最小总成本。

2 4
1 1 3
3 3 13
0 0 2
0 2 5
2 0 4
2 2 3

12

提示

样例 1 解释

使用第一种购物优惠，选择区域 $\{(x, y) \mid x \leq 1, y \geq 1\}$ 获取第二件商品。然后单独购买第 1、3、4 件商品。总成本为 $3 + (2 + 4 + 3) = 12$。

以下表格展示了 25 分的分布情况：

翻译由 DeepSeek V3 完成