AT_joi2026final_h かかし 2 (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 \leq i \leq 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 \leq 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 \geq 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 \leq 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 \geq 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`. ---

### Subtasks 1. ( $ 4 $ points) $ K = 1 $ ． 2. ( $ 6 $ points) $ K \leq 2 $ ． 3. ( $ 11 $ points) $ N \leq 500 $ ， $ K \leq 300 $ ． 4. ( $ 27 $ points) $ N \leq 6\,000 $ ． 5. ( $ 19 $ points) $ N \leq 75\,000 $ ． 6. ( $ 33 $ points) No additional constraints. --- ### Sample Explanation 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 Explanation 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 Explanation 3 This sample input satisfies the constraints of subtasks $ 3,4,5,6 $ . --- ### Sample Explanation 4 This sample input satisfies the constraints of subtasks $ 3,4,5,6 $ . ### Constraints - $ 1 \leq K \leq N \leq 200\,000 $ ． - $ T_i $ is one of $ 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 $ )． - Given values are all integers.