The moment of peace is fleeting, and the dark clouds of the apocalypse are closing in. Why fear a heartless fate? Beyond the limits, we hope for flowers to bloom.

To execute a mad plan to destroy the world, a mysterious man occupying the body of a deceased person has created countless Doomsday Towers on this blue planet. These towers emit dense aether rays, mentally controlling almost all living beings near them; only those with special protection are immune to the aether rays.

Some protected volunteer squads have investigated these towers. The results show that these towers form a complex aether transmission network, continuously absorbing aether from the earth and transmitting it to the central tower located in the Empire.

A team of heroes with special protection has decided to break into some of these towers to conduct a thorough investigation and attempt to destroy them. Once the heroes destroy the towers they enter, the aether transmission network will be affected. Therefore, everyone hopes to select some towers to destroy such that the maximum transmission capacity of the network is minimized.

As the vanguard of the squad breaking into the Doomsday Towers, you have reread all the information the team currently possesses. Whether this bold action plan will ultimately save the world is something no one can predict in advance. But for the future of this planet, we have no choice but to give it our all.

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, which constitute all nodes of the aether transmission network.

• The height of the towers is much smaller than the radius of the planet, so we consider the $i$-th tower ($1 \le i \le N$) as a point $(x_i, y_i, z_i)$ on the sphere. The aether transmission efficiency of the $i$-th tower is $q_i$.
• It is guaranteed that the positions of the $N$ towers are distinct. Among these $N$ towers, tower $s$ is the aether absorption point, and tower $t$ is the central tower located in the Empire; the aether concentration at these two towers is significantly higher than at the others, so only towers other than these two can be entered.

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

• Transmission channels are bidirectional, but the flow of aether per unit time must be unidirectional.
• To save unnecessary costs, the two ends of a transmission channel will not connect the same tower, and no two transmission channels will connect the same pair of towers.
• To reduce transmission distance, the $j$-th transmission channel is laid along the minor arc of the great circle where $u_j$ and $v_j$ are located. Thus, its length $r_j$ is the spherical distance between the two towers on the planet's surface. To avoid interference between transmission channels, for any minor arc corresponding to a transmission channel, the minor arcs corresponding to other transmission channels will only intersect with it at its two endpoints. It is guaranteed that the two towers connected by the same transmission channel are not antipodal points.
  • If you are unfamiliar with great circles, minor arcs, spherical distance, or antipodal points, you may refer to the Note section at the end of the problem.

Influenced by transmission efficiency and channel length, each transmission channel has its own upper limit for aether transmission capacity.

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

The entire aether transmission network needs to transmit the aether absorbed by tower $s$ to tower $t$ along the transmission channels, maximizing the aether transmission volume per unit time. To this end, the transmission network will automatically determine an aether transmission scheme that maximizes this volume while satisfying the capacity limits of all transmission channels.

• In other words, if the towers are viewed as vertices in a graph and the transmission channels as edges, with the capacity limits corresponding to the capacity of each edge, the aether transmission scheme should be exactly the maximum flow from $s$ to $t$.

Although no one can guarantee that breaking into the towers will lead to their destruction, as the vanguard of the squad, you want to calculate before setting off what the maximum transmission volume per unit time of the transmission network will be if you successfully destroy all the towers you intend to enter.

• If the selected towers are successfully destroyed, the capacity of all transmission channels connected to them will drop to $0$, while the capacity of other channels remains unchanged; the transmission network will then automatically adjust to a new scheme with the maximum transmission volume in the new network.
• In the ideal case, the squad will have the opportunity to investigate and destroy $L$ towers. Therefore, you need to select $L$ towers in advance (none of which can be $s$ or $t$) such that when these $L$ towers are successfully destroyed, the aether transmission volume of the new transmission scheme of the network is as small as possible.

Input

Read from standard input.

The first line contains five positive integers $N, M, L, s, t$ ($3\le N\le 1000$, $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 towers, the number of transmission channels, the number of towers that can be destroyed, the index of the main aether absorption tower, and the index of the central tower, respectively.

The second line contains two real numbers $R, K$ ($1\le R\le 10^3$, $1\le K\le 10^3$), representing the radius of the planet and the constant used to calculate aether capacity.

The next $N$ lines each contain 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 the information of the $i$-th tower, where $q_i$ is the transmission capability, and $a_i$ and $b_i$ describe the position: let $\theta_i = \pi a_i$, $\varphi_i = \pi b_i$, then $(x_i, y_i, z_i) = (R \sin\theta_i \cos\varphi_i, R\sin\theta_i \sin\varphi_i, R\cos\theta_i)$. It is guaranteed that the positions of the towers are distinct.

The last $M$ lines each contain two positive integers $u_i, v_i$ ($1\le u_i, v_i\le N$), representing the two towers connected by a transmission channel. It is guaranteed that the two towers connected by the same channel are not the same and are not antipodal, no two channels connect the same pair of towers, and the transmission network is connected.

All real numbers in the input are provided to 4 decimal places.

Output

Output to standard output.

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

Examples

Input 1

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

Output 1

8.105694691387022

Note 1

The aether transmission network is shown in the figure below. The blue sphere represents the planet's surface; the purple points are the towers, where $P_i$ corresponds to the $i$-th tower in the input; the yellow lines represent the transmission channels.

The original maximum transmission volume per unit time was $188/\pi^2$. Destroying either the 2nd or 5th tower reduces the maximum transmission volume to $80/\pi^2$, while destroying the 3rd or 4th tower only reduces it to $94/\pi^2$. Therefore, one should choose to destroy the 2nd or 5th tower.

Note

In three-dimensional space, we can describe the position of a point using an ordered triple of real numbers $(x, y, z)$, where $x, y, z$ are called the x-coordinate, y-coordinate, and z-coordinate, respectively.

A sphere in three-dimensional space with center $(x_0, y_0, z_0)$ and radius $R$ is the set of all points $(x, y, z)$ satisfying $(x-x_0)^2 + (y-y_0)^2+(z-z_0)^2=R^2$. For two distinct points $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$ on the sphere:

• If they are not antipodal points (two points are antipodal if and only if their Euclidean distance in space is $2R$), they and the center of the sphere are not collinear, and these three points uniquely determine a plane. The intersection of this plane and the sphere is called a "great circle". The arc of the great circle is divided into two parts by these two points, and the length of the shorter part is called the spherical distance between these two points on the sphere.
• If the two points are antipodal, their spherical distance is defined as $\pi R$.

Although this problem does not provide a direct visualization tool, you can use the convert.py file provided to convert files in the problem's input format into drawing commands that can be directly input into Geogebra. convert.py reads from standard input and outputs the converted drawing commands to standard output. For example, running convert.py with input redirected from 1.in produces:

$ python convert.py < 1.in
======= Commands begin =======

x^2+y^2+z^2=1^2

towers = {(1; 0.0 pi; -0.5000 pi), (1; 0.25 pi; -0.2500 pi), (1; 0.0 pi; 0.0000 pi), (1; 0.5 pi; 0.0000 pi), (1; 0.25 pi; 0.2500 pi), (1; 0.0 pi; 0.5000 pi)}

ulist = {1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5}

vlist = {2, 3, 4, 3, 4, 4, 5, 6, 5, 6, 6}

Zip(CircularArc(O, A, B), A, Zip(towers(i), i, ulist), B, Zip(towers(i), i, vlist))

Sequence(Text("Tower " + (i), towers(i), true), i, 1, 6)

======= Commands end =======

By pasting each line of instructions between ======= Commands begin ======= and ======= Commands end ======= into the input box of the algebra view in order, you can obtain a 3D object similar to the one in the appendix of Example 1. You may need to install Python 3.6 or higher to run convert.py.

This conversion tool is undoubtedly a selfless gift from the kind problem setter. The setter believes that this wonderful tool can provide powerful assistance on your journey to AC this problem.