Let There Be Light

Suppose there are some light sources and many spherical balloons. Every light source is small enough to be modeled as a point light source, and it emits light in all directions. The surfaces of the balloons absorb light and do not reflect it. Surprisingly, in this world balloons may overlap.

You want the total illumination intensity at an objective point to be as high as possible. To achieve this, some of the balloons that obstruct light can be removed. Because of removal costs, however, there is a limit on the number of balloons that may be removed. You would like to remove an appropriate set of balloons so as to maximize the illumination intensity at the objective point.

The input is a sequence of datasets. Each dataset is formatted as follows.

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

The first line of a dataset contains three positive integers $N$, $M$ and $R$, separated by a single space. $N$ is the number of balloons and does not exceed $2000$. $M$ is the number of light sources and does not exceed $15$. $R$ is the number of balloons that may be removed, which does not exceed $N$.

Each of the following $N$ lines contains four integers separated by a single space. $(S_{ix}, S_{iy}, S_{iz})$ is the center of the $i$-th balloon and $S_{ir}$ is its radius.

Each of the following $M$ lines contains four integers separated by a single space. $(T_{jx}, T_{jy}, T_{jz})$ is the position of the $j$-th light source and $T_{jb}$ is its brightness.

The last line of a dataset contains three integers separated by a single space. $(E_x, E_y, E_z)$ is the position of the objective point.

$S_{ix}$, $S_{iy}$, $S_{iz}$, $T_{jx}$, $T_{jy}$, $T_{jz}$, $E_x$, $E_y$ and $E_z$ are greater than $-500$ and less than $500$. $S_{ir}$ is greater than $0$ and less than $500$. $T_{jb}$ is greater than $0$ and less than $80000$.

At the objective point, the intensity of the light from the $j$-th light source, if no balloon interrupts it, is inversely proportional to the square of the distance, namely

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

The total illumination intensity is the sum of these contributions over the light sources that reach the objective point.

You may assume the following.

• The distance between the objective point and any light source is at least $1$.
• For every $i$ and $j$, even if $S_{ir}$ changes by $\varepsilon$ (with $|\varepsilon| < 0.01$), whether the $i$-th balloon hides the $j$-th light source or not does not change.

The end of the input is indicated by a line of three zeros.

For each dataset, output on its own line the maximum possible total illumination intensity at the objective point after removing at most $R$ balloons.

Because every coordinate, radius, and brightness is an integer, each light source that reaches the objective point contributes an intensity of the form $T_{jb}/D_j$ with an integer $D_j$, so the maximum total intensity is always a rational number. Print it as an exact reduced fraction p/q, where q is a positive integer, p is a non-negative integer, and $\gcd(p, q) = 1$. When the maximum intensity is $0$, print 0/1.