AT_joi2026final_h かかし 2 (Scarecrows 2)

JOI 村有一块广阔的田地。这块田地用无限的 $xy$ 平面表示，其中 $x$ 轴的正方向指向东，$y$ 轴的正方向指向北。 JOI 村的村长计划在田地里放置一些稻草人，以保护田地不受敌人侵害。每个稻草人根据其放置的位置和朝向，可以保护平面上的某个区域。 目前有 $N$ 个稻草人安置方案被提出，按 $1$ 到 $N$ 编号。执行第 $i$ 个方案（$1 \leq i \leq N$）需要花费 $C_i$。每个方案用三个整数 $T_i, X_i, Y_i$ 描述，含义如下： - 如果 $T_i = 1$，表示在点 $(X_i, Y_i)$ 放置一个面朝西的稻草人。该稻草人可以保护所有满足 $x \leq X_i$ 的点。 - 如果 $T_i = 2$，表示在点 $(X_i, Y_i)$ 放置一个面朝东的稻草人。该稻草人可以保护所有满足 $x \geq X_i$ 的点。 - 如果 $T_i = 3$，表示在点 $(X_i, Y_i)$ 放置一个面朝南的稻草人。该稻草人可以保护所有满足 $y \leq Y_i$ 的点。 - 如果 $T_i = 4$，表示在点 $(X_i, Y_i)$ 放置一个面朝北的稻草人。该稻草人可以保护所有满足 $y \geq Y_i$ 的点。 村长希望从这 $N$ 个方案中选出若干个执行，使得平面上的每个点都至少被 $K$ 个稻草人保护。在所有满足条件的选择中，总花费应当最小。保证 $N$ 个方案中，各自的 $(X_i, Y_i)$ 坐标互不相同。 给定这 $N$ 个方案的信息，判断是否可以选择一些方案，使得平面上每个点都至少被 $K$ 个稻草人保护。如果可以，请输出需要的最小总花费。

从标准输入读取以下数据。 > $N$ $K$ $T_1$ $X_1$ $Y_1$ $C_1$ $T_2$ $X_2$ $Y_2$ $C_2$ $\vdots$ $T_N$ $X_N$ $Y_N$ $C_N$

输出使得平面上每个点都至少被 $K$ 个稻草人保护所需的最小总花费。如果不存在满足条件的选择，输出 `-1`。

### 子任务 1. （$4$ 分）$K = 1$。 2. （$6$ 分）$K \leq 2$。 3. （$11$ 分）$N \leq 500$，$K \leq 300$。 4. （$27$ 分）$N \leq 6\,000$。 5. （$19$ 分）$N \leq 75\,000$。 6. （$33$ 分）无额外限制。 --- ### 样例解释 1 例如，假设执行了第 $3$ 个和第 $5$ 个方案。则稻草人的放置如下： - 在方案 $3$ 中，在点 $(36,73)$ 放置了一个面朝西的稻草人。花费为 $78$。 - 在方案 $5$ 中，在点 $(15,49)$ 放置了一个面朝东的稻草人。花费为 $21$。 这种情况下，平面上任意一点都至少被一个稻草人保护。例如，点 $(0,0)$ 被方案 $3$ 里面朝西的稻草人保护。总花费为 $78 + 21 = 99$。无法以更小的总花费使每个点至少被一个稻草人保护，所以输出应为 $99$。 该样例输入满足所有子任务的限制。 --- ### 样例解释 2 本例与样例输入 $1$ 的区别仅在于 $K$ 的值。由于无法使平面上每个点都至少被 $3$ 个稻草人保护，应输出 `-1`。 本样例输入满足子任务 $3,4,5,6$ 的限制。 --- ### 样例解释 3 本样例输入满足子任务 $3,4,5,6$ 的限制。 --- ### 样例解释 4 本样例输入满足子任务 $3,4,5,6$ 的限制。 ### 数据范围 - $1 \leq K \leq N \leq 200\,000$。 - $T_i$ 取 $1,2,3,4$ 之一（$1 \leq i \leq N$）。 - $0 \leq X_i \leq 10^9$（$1 \leq i \leq N$）。 - $0 \leq Y_i \leq 10^9$（$1 \leq i \leq N$）。 - $(X_i, Y_i) \neq (X_j, Y_j)$（$1 \leq i < j \leq N$）。 - $0 \leq C_i \leq 10^9$（$1 \leq i \leq N$）。 - 所有给定的值均为整数。 由 ChatGPT 5 翻译