在 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$ 的所有点。

村长希望选择并执行这些方案中的一部分，使得平面上的每一个点都至少被 $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 \le K \le N \le 200\,000$
• $T_i \in \{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 6\,000$
5. (19 分) $N \le 75\,000$
6. (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

说明 1

例如，假设执行方案 3 和 5。那么稻草人的放置情况如下： 在方案 3 中，在点 $(36, 73)$ 处放置一个朝西的稻草人。成本为 78。 在方案 5 中，在点 $(15, 49)$ 处放置一个朝东的稻草人。成本为 21。

在这种情况下，坐标平面上的每一个点都至少被一个稻草人保护。例如，点 $(0, 0)$ 被方案 3 中放置在 $(36, 73)$ 处朝西的稻草人保护。总成本为 $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

说明 2

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

样例输入 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

样例输入 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