P12971 [CCO 2025] Shopping Deals

你正在一家出售 $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$）。

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

**样例 1 解释** 使用第一种购物优惠，选择区域 $\{(x, y) \mid x \leq 1, y \geq 1\}$ 获取第二件商品。然后单独购买第 1、3、4 件商品。总成本为 $3 + (2 + 4 + 3) = 12$。 以下表格展示了 25 分的分布情况： | 分值 | $N$ 的范围 | $M$ 的范围 | 额外约束条件 | |:------:|:-----------------:|:------------------:|:---------------------------------------------------------------------------:| | 1 分 | $1 \leq N \leq 8$ | $1 \leq M \leq 20$ | 无 | | 3 分 | $1 \leq N \leq 70$ | $1 \leq M \leq 20$ | 无 | | 3 分 | $1 \leq N \leq 70$ | $1 \leq M \leq 70$ | 无 | | 4 分 | $1 < N \leq 100$ | $1 < M \leq 100000$ | 所有 $(a_i, b_i)$ 和 $(x_j, y_j)$ 点的 $x$ 或 $y$ 坐标互不相同 | | 2 分 | $1 \leq N \leq 100$ | $1 \leq M \leq 100000$ | 无 | | 8 分 | $1 \leq N \leq 1000$ | $1 \leq M \leq 100000$ | 所有 $(a_i, b_i)$ 和 $(x_j, y_j)$ 点的 $x$ 或 $y$ 坐标互不相同 | | 4 分 | $1 \leq N \leq 1000$ | $1 \leq M \leq 100000$ | 无 | 翻译由 DeepSeek V3 完成