빛이 있으라

몇 개의 광원과 여러 개의 구형 풍선이 있다고 합시다. 모든 광원은 점광원으로 모델링할 수 있을 만큼 작으며, 모든 방향으로 빛을 냅니다. 풍선의 표면은 빛을 흡수하며 반사하지 않습니다. 놀랍게도 이 세계에서는 풍선끼리 겹칠 수 있습니다.

당신은 목표 지점에서의 총 조도(illumination intensity)를 가능한 한 높이고 싶습니다. 이를 위해 빛을 가리는 풍선 중 일부를 제거할 수 있습니다. 그러나 제거 비용 때문에 제거할 수 있는 풍선의 수에는 제한이 있습니다. 목표 지점의 조도를 최대로 만들도록 적절한 풍선 집합을 제거하려고 합니다.

입력은 여러 개의 데이터셋으로 이루어집니다. 각 데이터셋의 형식은 다음과 같습니다.

N M R
S1x S1y S1z S1r
...
SNx SNy SNz SNr
T1x T1y T1z T1b
...
TMx TMy TMz TMb
Ex Ey Ez

데이터셋의 첫 줄에는 공백으로 구분된 세 양의 정수 $N$, $M$, $R$이 주어집니다. $N$은 풍선의 개수로 $2000$을 넘지 않습니다. $M$은 광원의 개수로 $15$를 넘지 않습니다. $R$은 제거할 수 있는 풍선의 개수로 $N$을 넘지 않습니다.

이어지는 $N$개의 줄에는 각각 공백으로 구분된 네 정수가 있습니다. $(S_{ix}, S_{iy}, S_{iz})$는 $i$번째 풍선의 중심이고 $S_{ir}$은 그 반지름입니다.

이어지는 $M$개의 줄에는 각각 공백으로 구분된 네 정수가 있습니다. $(T_{jx}, T_{jy}, T_{jz})$는 $j$번째 광원의 위치이고 $T_{jb}$는 그 밝기입니다.

데이터셋의 마지막 줄에는 공백으로 구분된 세 정수가 있습니다. $(E_x, E_y, E_z)$는 목표 지점의 위치입니다.

$S_{ix}$, $S_{iy}$, $S_{iz}$, $T_{jx}$, $T_{jy}$, $T_{jz}$, $E_x$, $E_y$, $E_z$는 $-500$보다 크고 $500$보다 작습니다. $S_{ir}$은 $0$보다 크고 $500$보다 작습니다. $T_{jb}$는 $0$보다 크고 $80000$보다 작습니다.

목표 지점에서 $j$번째 광원의 빛은, 이를 가리는 풍선이 없다면 거리의 제곱에 반비례하는 세기를 가집니다. 즉

$$\frac{T_{jb}}{(T_{jx}-E_x)^2 + (T_{jy}-E_y)^2 + (T_{jz}-E_z)^2}$$

총 조도는 목표 지점에 도달하는 광원들에 대한 이 값들의 합입니다.

다음을 가정해도 됩니다.

• 목표 지점과 임의의 광원 사이의 거리는 $1$ 이상입니다.
• 모든 $i$와 $j$에 대해, $S_{ir}$이 $\varepsilon$($|\varepsilon| < 0.01$)만큼 바뀌어도 $i$번째 풍선이 $j$번째 광원을 가리는지 여부는 바뀌지 않습니다.

입력의 끝은 세 개의 0으로 이루어진 줄로 표시됩니다.

각 데이터셋에 대해, 최대 $R$개의 풍선을 제거한 뒤 목표 지점에서 얻을 수 있는 최대 총 조도를 한 줄에 출력하세요.

모든 좌표, 반지름, 밝기가 정수이므로 목표 지점에 도달하는 각 광원은 정수 $D_j$에 대해 $T_{jb}/D_j$ 꼴의 세기를 기여하며, 따라서 최대 총 조도는 항상 유리수입니다. 이를 기약분수 p/q 형태로 출력하세요. 여기서 q는 양의 정수, p는 음이 아닌 정수이고 $\gcd(p, q) = 1$입니다. 최대 조도가 $0$이면 0/1을 출력하세요.