Minimizing Ether Transmission Flow via Tower Destruction

The planet is a perfect sphere with center at \( (0,0,0) \) and radius \( R \). On its surface there are \( N \) "apocalyptic towers" located at distinct points \( \left(x_i, y_i, z_i\right) \) with transmission efficiencies \( q_i \) for \( 1 \le i \le N \). Two of these towers, tower \( s \) and tower \( t \), play special roles: tower \( s \) is the ether absorption point and tower \( t \) is the imperial central tower. Due to their high ether concentrations, neither of these two towers can be destroyed.

The towers are connected by \( M \) bidirectional transmission channels. The \( j\text{-th} \) channel connects towers \( u_j \) and \( v_j \) along the minor arc of the great circle passing through them. Its length \( r_j \) is the spherical distance on the surface, computed as \[ r_j = R\cdot\arccos\Biggl(\frac{x_{u_j}x_{v_j}+y_{u_j}y_{v_j}+z_{u_j}z_{v_j}}{R^2}\Biggr), \] with the value clamped to ensure the argument of \( \arccos \) lies within \( [-1,1] \). It is guaranteed that the two towers connected by a channel are not antipodal. The capacity limit of channel \( j \) is given by \[ C_j = \frac{K\,q_{u_j}\,q_{v_j}}{r_j^2}. \]

The ether transmission network automatically routes ether from tower \( s \) to tower \( t \) according to the maximum flow formulation on this network.

You are the vanguard of a team planning to sabotage the network by destroying some towers. When a tower is destroyed (other than \( s \) or \( t \)), all transmission channels incident to it have their capacity dropped to \( 0 \). Your team has the opportunity to destroy exactly \( L \) towers (which must be chosen from towers other than \( s \) and \( t \)). You want to choose \( L \) towers such that, after their destruction, the new maximum flow from \( s \) to \( t \) is as small as possible. Compute this minimum possible maximum flow under an optimal choice of \( L \) towers to destroy.

Note: All formulas are in \( \LaTeX \) format.

inputFormat

The input is given as follows:

R K N M L s t
x₁ y₁ z₁ q₁
x₂ y₂ z₂ q₂
…
xₙ yₙ zₙ qₙ
u₁ v₁
u₂ v₂
…
uₘ vₘ

Where:

• \( R \) and \( K \) are constants (floating‐point numbers).
• \( N \) is the number of towers, and towers are numbered from \( 1 \) to \( N \).
• \( M \) is the number of transmission channels.
• \( L \) is the number of towers you are allowed to destroy. Note that towers \( s \) and \( t \) cannot be chosen for destruction.
• \( s \) and \( t \) are the indices of the special towers.
• For each tower, \( (x_i, y_i, z_i) \) represent its coordinates on the surface of the sphere (and it is guaranteed that \( x_i^2+y_i^2+z_i^2 = R^2 \)).
• Each transmission channel connects two distinct towers, and at most one channel connects any pair of towers.

outputFormat

Output a single floating‐point number representing the minimum possible maximum flow from tower \( s \) to tower \( t \) after destroying an optimal set of \( L \) towers. You may output any answer with an absolute or relative error of at most \( 10^{-6} \).

sample

10 1 4 4 1 1 4
10 0 0 2
0 10 0 1
0 0 10 1
-10 0 0 2
1 2
2 4
1 3
3 4

0.008107