K. Kenough Time
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ken lives on the beach in Barbieland and desperately wants to impress Barbie. One day when Barbie comes over, Ken sees $$$n$$$ drowning swimmers in the sea.

Barbieland is an infinite world where every position is denoted by floating point coordinates $$$(x, y)$$$. Any coordinate with $$$y \lt 0$$$ is sea, and anything else is land. Ken is initially at $$$(x_{\text{ken}}, y_{\text{ken}})$$$. There is also an ice cream stand at $$$(x_{\text{icecream}}, y_{\text{icecream}})$$$.

Ken's movement speed per second in units is capped by $$$v_{\text{run}}$$$ on land, and $$$v_{\text{swim}}$$$ on sea ($$$v_{\text{run}} \geq v_{\text{swim}}$$$).

To impress Barbie, Ken wants to save several drowning people. All of their $$$y$$$-coordinates are negative and they don't move, unless carried by Ken. Because there is no death in Barbieland, all he has to do is bring everyone to the ice cream stand to save them.

To carry a drowning person, Ken just has to swim to them. He can only drop them off at the ice cream stand, but thankfully, our hero has been hitting the gym, so he can carry $$$s$$$ ($$$1 \leq s \leq n$$$) swimmers simultaneously.

Can you help Ken save everyone as quickly as possible and bring everyone to the ice cream stand? Make sure to take a look at the comic below, which demonstrates that the most obvious solution may not be the fastest.

"Of course you get an ice cream cone for the swimmer too! You're not a monster." (xkcd 2821)
Input

The first line contains two integers, Ken's coordinates $$$(x_{\text{ken}}, y_{\text{ken}})$$$ ($$$-10^6 \leq x_{\text{ken}} \leq 10^6$$$, $$$0 \leq y_{\text{ken}} \leq 10^6$$$).

The second line contains two integers, the coordinates of the ice cream stand $$$(x_{\text{icecream}}, y_{\text{icecream}})$$$ ($$$-10^6 \leq x_{\text{icecream}} \leq 10^6$$$, $$$0 \leq y_{\text{icecream}} \leq 10^6$$$).

The third line contains two integers, Ken's running and swimming speeds $$$v_{\text{run}}$$$ and $$$v_{\text{swim}}$$$, respectively, both in units per second ($$$1 \leq v_{\text{swim}} \leq v_{\text{run}} \leq 100$$$).

The fourth line contains two integers, the number $$$n$$$ of drowning swimmers Ken has to save ($$$1 \leq n \leq 15$$$), and his strength $$$s$$$ ($$$1 \leq s \leq n$$$).

The next $$$n$$$ lines contain two integers each, the coordinates $$$(x_i, y_i)$$$ of the $$$i$$$-th drowning person ($$$-10^6 \leq x_{i} \leq 10^6$$$, $$$-10^6 \leq y_{i} \lt 0$$$).

Output

Output a single floating point number in decimal format, the time in seconds that Ken needs to save everyone. The result will be accepted as long as the absolute or relative error is at most $$$10^{-6}$$$.

Examples
Input
-2 2
3 3
2 1
1 1
2 -1
Output
5.7036530240
Input
0 0
0 0
1 1
4 3
-4 -2
-2 -4
2 -4
4 -2
Output
23.5453980697
Input
7 3
100 14
100 3
8 2
19 -2
50 -34
164 -12
8000 -613
-34 -4
-976 -115
-10780 -33
-10780 -34
Output
940.2817219035
Note

The first example is the set up in the comic above. There is only one swimmer drowning at $$$(2, -1)$$$ that we reach by running to $$$(\sim1.52, 0)$$$ and swimming to $$$(2, -1)$$$. Then, to get back to the ice cream stand, we swim to $$$(\sim2.14, 0)$$$ and run to $$$(3, 3)$$$.

In the second example, Ken starts at the ice cream stand, and swims as fast as he runs.