P15946 [JOI Final 2026] 稻草人 2 / Scarecrows 2

JOI 村有一片广阔的田地。田地由一个无限的 $xy$ 平面表示，$x$ 轴正方向为东，$y$ 轴正方向为北。 JOI 村的村长计划在田地里放置一些稻草人，以保护其免受敌人的侵害。 每个稻草人根据其位置和方向保护平面上的特定区域。 目前已经提出了 $N$ 个放置方案，编号从 $1$ 到 $N$。执行方案 $i$ $(1\le i\le N)$ 需要花费 $C_i$ 的代价。每个方案由三个整数 $T_i, X_i, Y_i$ 描述，如下所示： - 如果 $T_i=1$，一个面向西方的稻草人被放置在点 $(X_i, Y_i)$。该稻草人保护平面上满足 $x\le X_i$ 的所有点。 - 如果 $T_i=2$，一个面向东方的稻草人被放置在点 $(X_i, Y_i)$。该稻草人保护平面上满足 $x\ge X_i$ 的所有点。 - 如果 $T_i=3$，一个面向南方的稻草人被放置在点 $(X_i, Y_i)$。该稻草人保护平面上满足 $y\le Y_i$ 的所有点。 - 如果 $T_i=4$，一个面向北方的稻草人被放置在点 $(X_i, Y_i)$。该稻草人保护平面上满足 $y\ge 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 例如，假设执行方案 $3$ 和 $5$。那么稻草人的放置情况如下。 - 在方案 $3$ 中，一个面向西方的稻草人被放置在点 $(36, 73)$。代价为 $78$。 - 在方案 $5$ 中，一个面向东方的稻草人被放置在点 $(15, 49)$。代价为 $21$。 在这种情况下，坐标平面上的每个点都至少被一个稻草人保护。例如，点 $(0,0)$ 由方案 $3$ 中放置在 $(36, 73)$ 且面向西方的稻草人保护。总代价为 $78+21=99$。无法用更小的总代价使平面上的每个点都至少被一个稻草人保护，因此输出应为 $99$。 该样例输入满足所有子任务的限制。 ### 样例 2 此样例与样例输入 $1$ 的区别仅在于 $K$ 的值。由于无法用至少 $3$ 个稻草人保护坐标平面上的每个点，因此输出应为 $-1$。 该样例输入满足子任务 $3, 4, 5, 6$ 的限制。 ### 样例 3 该样例输入满足子任务 $3, 4, 5, 6$ 的限制。 ### 样例 4 该样例输入满足子任务 $3, 4, 5, 6$ 的限制。 ### 限制条件 - $1\le K\le N\le 200000$。 - $T_i$ 是 $1, 2, 3$ 或 $4$ 中的一个 $(1\le i\le N)$。 - $0\le X_i\le 10^{9}$ $(1\le i\le N)$。 - $0\le Y_i\le 10^{9}$ $(1\le i\le N)$。 - $(X_i, Y_i) \neq (X_j, Y_j)$ $(1\le i < j\le N)$。 - $0\le C_i\le 10^{9}$ $(1\le i\le N)$。 - 给定的值均为整数。 ### 子任务 1. (4 分) $K=1$。 2. (6 分) $K\le 2$。 3. (11 分) $N\le 500, K\le 300$。 4. (27 分) $N\le 6000$。 5. (19 分) $N\le 75000$。 6. (33 分) 无附加限制。