配点 : 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 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).
- 所有输入值都是整数。
小課題
- (5 点) K = 1,T_i \leqq 2 (1 \leqq i \leqq N).
- (7 点) K = 1.
- (7 点) K \leqq 2.
- (22 点) N \leqq 15.
- (35 点) N \leqq 500,K \leqq 300.
- (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 满足约束。 选择