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

#5144. 「CCO 2025」Shopping Deals

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

题目描述

译自 CCO 2025 Day2 T3「Shopping Deals」。

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

商店提供了 $N$ 个购物优惠。第 $i$ 个购物优惠由点 $(a_{i}, b_{i})$ 指定，支付费用 $c_{i}$ 后，你可以从以下四个区域中选择一个，获得该区域内的所有商品各一件：

• 点 $(x, y)$ 满足 $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}$ 的区域。

每个购物优惠最多只能使用一次。商品也可以通过支付其价格 $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

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

数据范围与提示

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