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$。

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

99

例如，假设执行方案 $3$ 和 $5$。那么稻草人的放置情况如下。

• 在方案 $3$ 中，一个面向西方的稻草人被放置在点 $(36, 73)$。代价为 $78$。
• 在方案 $5$ 中，一个面向东方的稻草人被放置在点 $(15, 49)$。代价为 $21$。

在这种情况下，坐标平面上的每个点都至少被一个稻草人保护。例如，点 $(0, 0)$ 由方案 $3$ 中放置在 $(36, 73)$ 且面向西方的稻草人保护。总代价为 $78 + 21 = 99$。无法用更小的总代价使平面上的每个点都至少被一个稻草人保护，因此输出应为 $99$。

该样例输入满足所有子任务的限制。

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

-1

此样例与样例输入 $1$ 的区别仅在于 $K$ 的值。由于无法用至少 $3$ 个稻草人保护坐标平面上的每个点，因此输出应为 $-1$。

该样例输入满足子任务 $3, 4, 5, 6$ 的限制。

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

315

该样例输入满足子任务 $3, 4, 5, 6$ 的限制。

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

328

该样例输入满足子任务 $3, 4, 5, 6$ 的限制。

限制条件

• $1 \leq K \leq N \leq 200000$。
• $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)$。
• 给定的值均为整数。

子任务

1. (4 分) $K = 1$。
2. (6 分) $K \leq 2$。
3. (11 分) $N \leq 500, K \leq 300$。
4. (27 分) $N \leq 6000$。
5. (19 分) $N \leq 75000$。
6. (33 分) 无附加限制。