AT_caddi2019_a.球の詰め込み

有一个 $ L \times L \times L $ 的立方体形状的容器。在这个容器里进行装填球体的游戏。

容器中的点使用直角坐标系表示，一个角点的坐标是 $ (0, 0, 0) $，与它最远的另一个顶点的坐标是 $ (L, L, L) $。

有 $ N $ 个球可以用来填充容器，分别称为球 $ 1 $、球 $ 2 $、......、球 $ N $。每个球 $ i $ 的半径为 $ R_i $。

你可以选择任意数量的球，将它们的中心放置在容器中的任意整数坐标上。

放置球时，球可以悬空，但不能超出容器边界，也不能彼此重叠（球与容器或球之间接触是允许的）。

这次球的配置得分由以下两部分组成：

• 基础分：每个球 $ i $ 有一个基础分 $ P_i $，将其放入容器即可获得 $ P_i $ 分。
• 奖励分：存在 $ M $ 对球在靠近放置时可以获得额外奖励分。具体来说，给出 $ M $ 个四元组 $ (A_i, B_i, C_i, D_i) $，它表示如果球 $ A_i $ 和球 $ B_i $ 的中心之间的距离不超过 $ C_i $，则可以得到 $ D_i $ 的奖励分。

请尽量提高你的总得分。不需要找到最优解。

输入为：

$ L $ $ N $ $ M $ $ R_1 $ $ P_1 $ $ R_2 $ $ P_2 $ $ : $ $ R_N $ $ P_N $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ D_2 $ $ : $ $ A_M $ $ B_M $ $ C_M $ $ D_M $

对每个球 $ i $ 的中心坐标 $ (X_i, Y_i, Z_i) $，输出以下格式。如果某个球不放在容器内，则其中心坐标应输出为 $ (-1, -1, -1) $。

$ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ : $ $ X_N $ $ Y_N $ $ Z_N $

以下情况会被判定为 Wrong Answer：

• 输出格式不正确（包括 $ X_i, Y_i, Z_i $ 中任一值不是整数）。
• 球超出容器边界，即对于放置在容器内的球 $ i $，如果 $ X_i - R_i $, $ Y_i - R_i $, $ Z_i - R_i $ 中任一值小于 $ 0 $，或 $ X_i + R_i $, $ Y_i + R_i $, $ Z_i + R_i $ 中任一值大于 $ L $。
• 球之间有重叠，即对于放置在容器内的任意两个球 $ i $ 和 $ j $（$ i < j $），若球 $ i $ 和球 $ j $ 的中心之间的距离小于 $ R_i + R_j $。

数据范围

• $ L = 1000 $
• $ N = 1000 $
• $ M = 100000 $
• $ 1 \leq R_i \leq 200 $
• $ 1 \leq P_i \leq 80000 $
• $ 1 \leq A_i < B_i \leq N $
• $ 1 \leq C_i \leq 600 $
• $ 1 \leq D_i \leq 80000 $

输入中的所有值都是整数。

本翻译由 AI 自动生成