P15946 Scarecrows 2

There is a vast field in JOI Village. The field is represented by the infinite $xy$-plane, where the positive direction of the $x$-axis is East and the positive direction of the $y$-axis is North. The mayor of JOI Village plans to place several scarecrows in the field in order to protect it from enemies. Each scarecrow protects a certain region of the plane depending on its position and direction. Currently, $N$ placement plans have been proposed, numbered from $1$ to $N$. Executing plan $i$ $(1\le i\le N)$ requires a cost of $C_i$. Each plan is described by three integers $T_i,X_i,Y_i$ as follows. - If $T_i=1$, a scarecrow is placed at the point $(X_i,Y_i)$ facing West. This scarecrow protects all points on the plane satisfying $x\le X_i$. - If $T_i=2$, a scarecrow is placed at the point $(X_i,Y_i)$ facing East. This scarecrow protects all points on the plane satisfying $x\ge X_i$. - If $T_i=3$, a scarecrow is placed at the point $(X_i,Y_i)$ facing South. This scarecrow protects all points on the plane satisfying $y\le Y_i$. - If $T_i=4$, a scarecrow is placed at the point $(X_i,Y_i)$ facing North. This scarecrow protects all points on the plane satisfying $y\ge Y_i$. The mayor wants to select and execute some of these $N$ plans so that every point on the plane is protected by at least $K$ scarecrows. Among all such choices, the total cost should be minimized. It is guaranteed that the coordinates $(X_i,Y_i)$ are pairwise distinct among the $N$ plans. Given the information of the $N$ plans, determine whether it is possible to select plans so that every point on the plane is protected by at least $K$ scarecrows. If it is possible, output the minimum possible total cost of the selected plans.

Read the following data from the standard input. > $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$

Output the minimum total cost required so that every point on the plane is protected by at least $K$ scarecrows. If there is no way to choose the plans so that the condition is satisfied, output $-1$.

### Sample 1 For example, suppose that plans $3$ and $5$ are executed. Then the scarecrows are placed as follows. - In plan $3$, one scarecrow is placed at the point $(36,73)$ facing West. The cost is $78$. - In plan $5$, one scarecrow is placed at the point $(15,49)$ facing East. The cost is $21$. In this case, every point on the coordinate plane is protected by at least one scarecrow. For example, the point $(0,0)$ is protected by the scarecrow placed at $(36,73)$ facing West in plan $3$. The total cost is $78+21=99$. It is impossible to protect every point on the plane with at least one scarecrow with a smaller total cost, so the output should be $99$. This sample input satisfies the constraints of all subtasks. ### Sample 2 This example differs from Sample Input $1$ only in the value of $K$. Since it is impossible to protect every point on the coordinate plane with at least $3$ scarecrows, the output should be $-1$. This sample input satisfies the constraints of subtasks $3,4,5,6$. ### Sample 3 This sample input satisfies the constraints of subtasks $3,4,5,6$. ### Sample 4 This sample input satisfies the constraints of subtasks $3,4,5,6$. ### Constraints - $1\le K\le N\le 200000$. - $T_i$ is one of $1,2,3$, or $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)$ ≠ $(X_j,Y_j)$ $(1\le i$ < $j\le N)$. - $0\le C_i\le 10^{9}$ $(1\le i\le N)$. - Given values are all integers. ### Subtasks 1. (4 points) $K=1$. 2. (6 points) $K\le 2$. 3. (11 points) $N\le 500,K\le 300$. 4. (27 points) $N\le 6000$. 5. (19 points) $N\le 75000$. 6. (33 points) No additional constraints.