题目描述

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

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

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

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

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

提示

样例 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 分) 无附加限制。