問題文

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 体以上のかかしによって守られているようにすることが可能かどうか判定し，可能な場合は実行する計画の合計コストの最小値を求めるプログラムを作成せよ．

制約

• 1 \leqq K \leqq N \leqq 6\,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. (5 点) K = 1，T_i \leqq 2 (1 \leqq i \leqq N)．
2. (7 点) K = 1．
3. (7 点) K \leqq 2．
4. (22 点) N \leqq 15．
5. (35 点) N \leqq 500，K \leqq 300．
6. (24 点) 追加の制約はない．

入力例 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 を出力する．

この入力例は小課題 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

この入力例は小課題 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

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