4491: 三角障碍
题目描述
Nanarikom 正在游玩名为 osu! 的音乐游戏。
Nanarikom 发现 osu! 的 logo 上有许多大小不一的正三角形，因此，Nanarikom 突发奇想想要计算以下问题。
Nanarikom 首先定义了一个正三角形网格 \triangle ABC△ABC，具体地：
- \triangle ABC△ABC 是一个底边水平的正三角形，由若干边长为 11 的正三角形拼合而成，总边长为 WW；
- 现在，根据所在行的不同，按照从上至下的顺序为顶点分配 [0, W][0,W] 的行号；
- 其中，对于第 ii 行的顶点，按照从左至右的顺序为顶点分配 [0, i][0,i] 的列号；
- 因此，对于每个顶点，我们都可以使用行号与列号的二元组 (x, y)(x,y) 描述其位置。
现在，Nanarikom 想要在 \triangle ABC△ABC 内摆放若干障碍物。候选项是 nn 个大小和位置不一的、底边水平的正三角形。第 ii 个障碍物的信息可以使用参数 (x_i, y_i, \mathit{siz}_i, w_i)(xi,yi,sizi,wi) 描述，其中：
- x_i, y_ixi,yi 代表该障碍物的上顶点所在的坐标为 (x_i, y_i)(xi,yi)；
- \mathit{siz}_isizi 代表该障碍物的边长；
- w_iwi 代表摆放该障碍物所需花费的代价；
- 障碍物摆放在与其他障碍物部分或完全重叠的位置上是可能的；
- 输入数据保证障碍物在 \triangle ABC△ABC 内部（可能与 \triangle ABC△ABC 的边界相交，但不会与 A, B, CA,B,C 三者中的任何一者相交）。
现在，Nanarikom 想要计算，如何选择一个候选障碍物的子集，使得 AA, BB, CC 三者中的任意二者都不能相互连接，且该子集的总代价尽可能小。请你告诉 Nanarikom 最小总代价的值；如果不存在可行的子集，请输出 -1−1。
其中，对于两个顶点 XX, YY，如果存在一条两端点分别为 XX, YY 的曲线，使得该曲线与任意障碍物的交集为空，且该曲线的非端点部分与 \triangle ABC△ABC 边界的交集为空，则称 XX, YY 可以相互连接；否则，XX, YY 不能相互连接。
你需要回答 Nanarikom 的 TT 组询问。
输入格式
第一行包含一个整数 TT（1 \leq T \leq 10001≤T≤1000），代表测试数据组数。对于每组测试数据：
- 第一行包含两个整数 nn, WW（1 \leq n \leq 10001≤n≤1000, 3 \leq W \leq 10^53≤W≤105），分别代表候选障碍物的数量和 \triangle ABC△ABC 的边长；
- 接下来的 nn 行中，第 ii 行包含四个整数 x_i, y_i, \mathit{siz}_i, w_ixi,yi,sizi,wi（0 \leq y_i \leq x_i \leq W0≤yi≤xi≤W, 1 \leq \mathit{siz}_i, w_i \leq 10^51≤sizi,wi≤105），代表每个障碍物的参数。
输入数据保证，至多只有 55 组测试数据使得 n > 100n>100。
输出格式
输入样例 复制
2
3 4
3 1 1 10
1 1 2 10
1 0 2 10
3 4
3 1 1 10
2 2 1 10
1 0 1 10输出样例 复制
30
-1数据范围与提示
对于第一组样例和第二组样例，相应的示意图分别如下：
