H - かかし 2 (Scarecrows 2) Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

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.

Input

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

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.

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.

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 Input 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

Sample Output 1

99

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 Input 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

Sample Output 2

-1

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 Input 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

Sample Output 3

315

This sample input satisfies the constraints of subtasks 3,4,5,6.

Sample Input 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

Sample Output 4

328

This sample input satisfies the constraints of subtasks 3,4,5,6.

配点： 100 点

問題文

JOI 村には，広大な畑がある． この畑は無限に広がる xy 座標平面で表され，x 軸正の向きが東方向，y 軸正の向きが北方向である．

JOI 村の村長は，畑を外敵から守るために，畑にいくつかのかかしを配置しようと考えている． 配置されたそれぞれのかかしは，その場所と向きに応じて，平面上の特定の領域を守ることができる．

現在，かかしを配置するための N 個の計画が提案されており，1 から N までの番号が付けられている． 計画 i (1\leqq i\leqq N) を実行するために必要なコストは C_i であり，その内容は整数 T_i, X_i, Y_i を用いて以下のように表される．

  • T_i = 1 のとき，かかし 1 体を点 (X_i,Y_i) に西向きに配置する．このかかしは平面上の x \leqq X_i の領域を守る．
  • T_i = 2 のとき，かかし 1 体を点 (X_i,Y_i) に東向きに配置する．このかかしは平面上の x \geqq X_i の領域を守る．
  • T_i = 3 のとき，かかし 1 体を点 (X_i,Y_i) に南向きに配置する．このかかしは平面上の y \leqq Y_i の領域を守る．
  • T_i = 4 のとき，かかし 1 体を点 (X_i,Y_i) に北向きに配置する．このかかしは平面上の y \geqq Y_i の領域を守る．

村長は，これらの N 個の計画のうちいくつかを選んで実行することで，できるだけ少ない合計コストで，平面上のどの点も K 体以上のかかしによって守られているようにしたいと考えている．ただし，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 \leqq K \leqq N \leqq 200\,000．
  • T_i は 1, 2, 3, 4 のいずれかである (1 \leqq i \leqq N)．
  • 0 \leqq X_i \leqq 10^9 (1 \leqq i \leqq N)．
  • 0 \leqq Y_i \leqq 10^9 (1 \leqq i \leqq N)．
  • (X_i, Y_i) \neq (X_j, Y_j) (1 \leqq i < j \leqq N)．
  • 0 \leqq C_i \leqq 10^9 (1 \leqq i \leqq N)．
  • 入力される値はすべて整数である．

小課題

  1. (4 点) K = 1．
  2. (6 点) K \leqq 2．
  3. (11 点) N \leqq 500，K \leqq 300．
  4. (27 点) N \leqq 6\,000．
  5. (19 点) N \leqq 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

例えば計画 3,5 を実行すると，以下のようにかかしが配置される．

  • 計画 3 では，かかし 1 体を点 (36,73) に西向きに配置する．コストは 78 である．
  • 計画 5 では，かかし 1 体を点 (15,49) に東向きに配置する．コストは 21 である．

このとき，座標平面上のどの点も 1 体以上のかかしで守られている．例えば，点 (0, 0) は計画 3 で点 (36,73) に西向きに配置したかかしによって守られている． また，合計コストは 78+21=99 である． これより少ない合計コストで平面上のすべての点を 1 体以上のかかしで守ることはできないので，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

入力例 1 とは K の値のみが異なる．

座標平面上のすべての点を 3 体以上のかかしによって守ることはできないため，-1 を出力する．

この入力例は小課題 3,4,5,6 の制約を満たす．

入力例 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

この入力例は小課題 3,4,5,6 の制約を満たす．

入力例 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

この入力例は小課題 3,4,5,6 の制約を満たす．