分数: 100 点
问题陈述
JOI村有一片广阔的田野。 场用无穷大来表示 xy- 平面,其中正方向 x- 轴为东且正方向 y- 轴为北。
JOI村村长计划在田野里放置几个稻草人,以保护村子免受敌人的侵害。 每个稻草人根据其位置和方向保护平面的特定区域。
目前, N 安置计划已提出,编号为 1 to N。 执行计划 i (1 \leq i \leq N) 需要成本 C_i。 每个计划由三个整数描述 T_i, X_i, Y_i 如下。
- If T_i = 1,在该点放置一个稻草人 (X_i, Y_i) 面向西。 这个稻草人保护平面上的所有点满足 x \leq X_i.
- If T_i = 2,在该点放置一个稻草人 (X_i, Y_i) 面向东。 这个稻草人保护平面上的所有点满足 x \geq X_i.
- If T_i = 3,在该点放置一个稻草人 (X_i, Y_i) 朝南。 这个稻草人保护平面上的所有点满足 y \leq Y_i.
- If T_i = 4,在该点放置一个稻草人 (X_i, Y_i) 朝北。 这个稻草人保护平面上的所有点满足 y \geq Y_i.
市长想要选择并执行其中一些 N 计划使平面上的每个点至少受到保护 K 稻草人。 在所有这些选择中,总成本应该最小化。 保证坐标 (X_i, Y_i) 之间成对不同 N 计划。
鉴于信息 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 \leq K \leq N \leq 200\,000.
- T_i 是其中之一 1, 2, 3, or 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).
- 给定值均为整数。
子任务
- (4 点) K = 1.
- (6 点) K \leq 2.
- (11 点) N \leq 500,K \leq 300.
- (27 点) N \leq 6\,000.
- (19 点) N \leq 75\,000.
- (33 点)没有额外的限制。
示例输入 1
7 1 2 45 21 96 1 5 85 70 1 36 73 78 1 28 12 80 2 15 49 21 1 45 11 96 2 63 26 19
示例输出 1
99
例如,假设计划 3 和 5 被执行。 然后稻草人的放置方式如下。
- 计划中 3,在该点放置一个稻草人 (36,73) 面向西。 成本是 78.
- 计划中 5,在该点放置一个稻草人 (15,49) 面向东。 成本是 21.
在这种情况下,坐标平面上的每个点都被至少一个稻草人保护。 例如,点 (0,0) 受到放置在的稻草人的保护 (36,73) 计划面向西 3。 总成本是 78 + 21 = 99。 用至少一个稻草人以较小的总成本保护平面上的每个点是不可能的,所以输出应该是 99.
此示例输入满足所有子任务的约束。
示例输入 2
7 3 2 45 21 96 1 5 85 70 1 36 73 78 1 28 12 80 2 15 49 21 1 45 11 96 2 63 26 19
示例输出 2
-1
此示例与示例输入不同 1 仅在值 K。
由于不可能至少保护坐标平面上的每个点 3 稻草人,输出应该是 -1.
此示例输入满足子任务的约束 3,4,5,6.
示例输入 3
19 5 2 36 42 64 2 7 89 74 1 0 15 82 1 10 63 55 2 58 28 19 2 45 91 3 2 2 34 97 1 7 55 82 1 17 12 17 2 59 76 82 1 7 4 68 2 51 98 47 1 51 21 38 2 19 0 72 1 73 73 11 2 62 19 74 1 45 7 94 1 79 32 21 1 85 50 21
示例输出 3
315
此示例输入满足子任务的约束 3,4,5,6.
示例输入 4
8 3 4 4 21 80 2 59 65 69 4 63 36 3 2 29 13 23 1 37 45 95 2 79 14 89 3 91 54 76 1 85 46 62
示例输出 4
328
此示例输入满足子任务的约束 3,4,5,6.