AT_joig2026final_g かかし 2 (Scarecrows 2)

在 JOI 村有一块广阔的农田。这片农田可用无限延伸的 $xy$ 坐标平面表示，$x$ 轴正方向为东，$y$ 轴正方向为北。 村长为了保护农田免受外敌入侵，计划在农田中布置若干稻草人。每个被布置的稻草人，可以根据其放置的位置和朝向，守护平面上的特定区域。 目前共有 $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$ 份计划中每个稻草人的放置坐标均不相同。 现在给出所有布置计划的信息，请编程判断是否有办法选择若干计划，使得平面上任意一点都被至少 $K$ 个稻草人守护；如果可以，请输出实现目标的最小总代价。

输入按照以下格式从标准输入读入。 > $N\ K$ > $T_1\ X_1\ Y_1\ C_1$ > $T_2\ X_2\ Y_2\ C_2$ > ⋮ > $T_N\ X_N\ Y_N\ C_N$

输出为了让平面上每个点都被至少 $K$ 个稻草人守护所需的最小总代价。如果不存在满足条件的计划组合，则输出 $-1$。

## 小子任务 1.（$5$ 分）$K=1$，且 $T_i \leq 2$（$1 \leq i \leq N$）。 2.（$7$ 分）$K=1$。 3.（$7$ 分）$K \leq 2$。 4.（$22$ 分）$N \leq 15$。 5.（$35$ 分）$N \leq 500$，$K \leq 300$。 6.（$24$ 分）无附加限制。 --- ## 样例解释 1 例如，如果选择计划 $3, 5$ 执行，稻草人的配置如下： - 计划 $3$：在 $(36,73)$ 放置一只朝西的稻草人，花费 $78$。 - 计划 $5$：在 $(15,49)$ 放置一只朝东的稻草人，花费 $21$。 此时，坐标平面上任意一点都至少被 $1$ 个稻草人守护。例如，点 $(0,0)$ 被由计划 $3$ 在 $(36,73)$ 处朝西布置的稻草人守护。总代价为 $78+21=99$。无法用更小的代价实现目标，因此应输出 $99$。 该输入例满足所有小子任务的约束。 --- ## 样例解释 2 与输入样例 1 仅 $K$ 的值不同。 无法让平面上的每个点都被至少 $3$ 个稻草人守护，因此输出 $-1$。 此输入例满足小子任务 $4, 5, 6$ 的约束。 --- ## 样例解释 3 此输入例满足小子任务 $5, 6$ 的约束。 --- ## 样例解释 4 此输入例满足小子任务 $4, 5, 6$ 的约束。 # 约束条件 - $1 \leq K \leq N \leq 6\,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 < j \leq N$ 时有 $(X_i, Y_i) \neq (X_j, Y_j)$）。 - $0 \leq C_i \leq 10^9$（$1 \leq i \leq N$）。 - 输入的所有值均为整数。 由 ChatGPT 5 翻译