1165 : 戴森球计划

Description

戴森球是弗里曼·戴森假想出的包围母恒星的巨大球形结构，它可以捕获大部分或者全部的恒星能量输出。戴森认为戴森球是长期生存技术文明对于能量需求增长的必然需求，并认为寻找其存在的证据可以引导发现的先进和智慧的外星生命。不同类型的戴森球和它们的能量收集能力将对应于在卡尔达肖夫指数水平上的技术进步。 —— 维基百科

X星人计划在一系列候选恒星中选择一个，以其为中心 (sx, sy, sy) 建设戴森球。首先对宇宙某片区域进行了扫描，记录了一系列已观测行星坐标(px, py, pz) 及其质量 v。根据测算，计划建设的戴森球将需要利用 w 单位行星质量，这决定了运输舰的工作半径 r，即选定的恒星中心半径 r（包括边缘）范围内行星质量不小于 w。为缩短工期，X星人希望选择合适的恒星，使运输舰工作半径 r 最小。

为简化建模，r只取 整数 ，行星与恒星当作 质点 ，不考虑其体积，位置随机分布。

Input

不超过20组测试数据，每组数据第一行三个整数 n, m, w 分别表示行星数量、候选恒星数量以及建设戴森球至少需要的行星质量。

接下来 n 行每行四个整数 (px_i, py_i, pz_i, v_i) 表示每个行星的坐标及其质量。

紧接着 m 行每行三个整数 (sx_i, sy_i, sz_i) 表示每个候选恒星的坐标。

其中 1 ≤ n ≤ 10⁵，1 ≤ m ≤ 10⁴，1 ≤ px_i, py_i, pz_i, v_i, sx_i, sy_i, sz_i, w ≤ 10⁹ 。

5 组数据达到最大规模，其余组所有数据范围在 500 以内。

Output

每组数据输出一行，一个整数，表示不同恒星方案中最小的运输舰工作半径r。如果所有观测到的行星质量之和都不足以支持本次戴森球计划，则输出 -1。

Sample

3 1 10
1 1 1 5
1 1 2 5
1 1 3 5
1 1 6
3 3 19
3 1 2 6
3 2 9 8
8 10 6 6
7 7 3
4 2 3
2 9 6

4
9

Hint

Source

Author

CSGrandeur