Background

Peace will vanish in an instant, and dark clouds of doom are waiting for a chance to strike. Why fear a merciless fate? Push beyond the limit and hope for flowers to bloom.

To carry out a crazy plan to destroy the world, a mysterious man who has taken over the body of a dead person has created countless Doomsday Towers on this blue planet. These towers emit dense ether rays, which mentally control almost all creatures near them. Only people with special blessings can avoid being controlled by the ether rays.

Some volunteer teams with blessings investigated these towers, and the results show that the Doomsday Towers form a complex ether transmission network. The network continuously absorbs ether from the ground and transmits it to the central tower of the empire.

A team of heroes with special blessings decides to break into some Doomsday Towers, in order to fully investigate them and try to destroy them. After the heroes destroy the towers they enter, the ether transmission network will be affected. Therefore, everyone hopes to choose some towers such that, after destroying them, the maximum transmission capacity of the network becomes as small as possible.

As the vanguard of the team storming the Doomsday Towers, you read again all the information currently known to the team. Whether this bold action plan can ultimately save the world is something no one can predict right now. But for the future of this planet, we can only gamble everything.

Problem Description

The surface of the planet is a perfect sphere centered at $(0, 0, 0)$ with radius $R$. There are $N$ Doomsday Towers on the surface of the planet, and these terrifying towers form all nodes of the ether transmission network.

• The height of the towers is much smaller than the planet radius, so we treat tower $i\ (1 \le i \le N)$ as a point $\left(x_i, y_i, z_i\right)$ on the sphere. The ether transmission efficiency of tower $i$ is $q_i$.
• It is guaranteed that the positions of the $N$ towers are pairwise distinct. Among these $N$ towers, tower $s$ is the ether absorption point, and tower $t$ is the central tower of the empire. The ether concentration of these two towers is significantly higher than that of the other towers, so you can only break into towers other than these two.

There are $M$ transmission channels between the $N$ towers. Channel $j\ (1 \le j \le M)$ connects towers $u_j$ and $v_j$, allowing them to transmit ether to each other.

• Transmission channels are bidirectional, but within each unit time, the flow direction of ether must be one-way.
• To save unnecessary costs, the two ends of a channel do not connect the same tower, and there are no two channels connecting the same pair of towers.
• To reduce transmission distance, channel $j$ is laid along the minor arc of the great circle determined by $u_j$ and $v_j$, so its length $r_j$ is the spherical surface distance between the two towers. To avoid interference between channels, for the minor arc corresponding to any channel, the minor arcs corresponding to other channels intersect it only at its two endpoints. It is guaranteed that the two towers connected by the same channel are not antipodal points.
  • If you do not know what a great circle, minor arc, spherical distance, or antipodal points are, you can refer to the hint section at the end of the statement.

Affected by transmission efficiency and channel length, each channel has its own upper bound on ether capacity.

• Specifically, within each unit time, the capacity upper bound of channel $j$ is $\frac{Kq_{u_j} q_{v_j}}{r_j^2}$, where $K$ is a given constant, $q_{u_j}, q_{v_j}$ are the transmission efficiencies of the towers at the two ends of the channel, and $r_j$ is the length of this channel.

The entire ether transmission network needs to transmit the ether absorbed by tower $s$ to tower $t$ along the channels, and make the ether transmission amount per unit time as large as possible. To do this, the network will automatically determine an ether transmission plan, maximizing this amount while satisfying all channel capacity upper bounds.

• In other words, if we view the towers as vertices of a graph, the channels as edges, and the capacity upper bounds as edge capacities, then the ether transmission plan is exactly the maximum flow from $s$ to $t$.

Although no one can guarantee that breaking into a Doomsday Tower will surely destroy it, as the vanguard you still want to compute in advance: if all towers you plan to break into are successfully destroyed, how much will the maximum transmission amount per unit time of the network drop to?

• If the selected towers are successfully destroyed, then the capacities of all channels incident to them will drop to $0$, and the capacities of the other channels remain unchanged. Then the network will automatically adjust to a new plan that maximizes the transmission amount in the new network.
• In the most ideal case, the team will have the chance to investigate and destroy $L$ Doomsday Towers. Therefore, you need to choose $L$ towers in advance (none of them can be $s$ or $t$), such that when these $L$ towers are all successfully destroyed, the ether transmission amount of the new plan is as small as possible.

Input Format

The first line contains five positive integers $N, M, L, s, t$（$3\le N\le 500$，$2\le M\le \frac{N(N-1)}{2}$，$1\le L\le \min\{8,N-2\}$，$1\le s, t\le N$）, representing the number of Doomsday Towers in the network, the number of transmission channels, the number of towers you have a chance to break into, the index of the main ether absorption tower, and the index of the central tower.

The second line contains two real numbers $R, K$（$1\le R\le 10^3$，$1\le K\le 10^3$）, representing the planet radius and the constant used when computing ether capacity.

In the next $N$ lines, each line contains three real numbers $a_i, b_i, q_i$（$0\le a_i\le 1$，$0\le b_i< 2$，$1\le q_i \le 10^3$）, describing tower $i$, where $q_i$ is the transmission capability of tower $i$, and $a_i$ and $b_i$ together describe the tower position: let $\theta_i = \pi a_i$, $\varphi_i = \pi b_i$ (if you are used to degrees instead of radians, you can replace $\pi$ with $180^\circ$), then $\left(x_i, y_i, z_i\right) = \left(R \sin\theta_i \cos\varphi_i, R\sin\theta_i \sin\varphi_i, R\cos\theta_i\right)$. It is guaranteed that the tower positions are all distinct.

In the last $M$ lines, each line contains two positive integers $u_i, v_i$（$1\le u_i, v_i\le N$）, indicating a transmission channel connecting the two towers. It is guaranteed that the two towers connected by the same channel are distinct and not antipodal points, no two channels connect the same pair of towers, and the transmission network is connected.

All real numbers in the input are given with $4$ digits after the decimal point.

Output Format

Output one real number, representing the maximum transmission amount per unit time of the new transmission network if the towers you plan to break into are successfully destroyed. Your output is considered correct if the relative error or absolute error compared to the standard output does not exceed $10^{-6}$.

6 11 1 1 6
1.0000 1.0000
1.0000 0.0000 10.0000
0.7500 0.2500 6.0000
0.5000 0.0000 1.0000
0.5000 0.5000 1.0000
0.2500 0.2500 6.0000
0.0000 0.0000 10.0000
1 2
1 3
1 4
2 3
2 4
3 4
3 5
3 6
4 5
4 6
5 6

8.105694691387022

Hint

Explanation for Sample #1

The ether transmission network is shown in the figure below. The blue sphere is the planet surface; the purple points are the Doomsday Towers, where $P_i$ corresponds to tower $i$ in the input; the yellow lines are the transmission channels.

The original maximum transmission amount per unit time is $188/\pi^2$. Destroying tower $2$ or tower $5$ can reduce the new maximum transmission amount per unit time to $80/\pi^2$, while destroying tower $3$ or tower $4$ can only reduce it to $94/\pi^2$. Therefore, you should choose tower $2$ or tower $5$ to attempt to destroy.

Translated by ChatGPT 5