Problem J
Cat and Mice

Photo by katie_mccolgan/Flickr

Everyone knows that cats love to eat mice. Naturally, when given the opportunity, any cat wants to eat as many mice as possible.

It just so happens that Cartesian Cat lives on the Cartesian Plane with her home located at $(0, 0)$. Obviously, none of the mice live at this location, they are smarter than that! However, the mice aren’t terribly smart. They live on the plane with Cartesian Cat and at time $t = 0$, stick their heads above the ground, in sight of Cartesian Cat. Each of the mice stays in sight at its location for a specified amount of time before ducking back underground, where Cartesian Cat can’t get it.

Cartesian Cat has a plan. At time $t = 0$, she’ll run straight towards a mouse, eat it instantaneously, and then head for another mouse, repeating the sequence until all the mice are eaten. She encounters two problems however: each time she eats a mouse her velocity reduces (due to her increased mass) by a constant multiplicative factor, $m$. That is, if her velocity is $v$ before eating a mouse, then after eating the mouse her velocity is $v\cdot m$. Also, if she doesn’t reach a mouse before it ducks underground, she won’t be able to eat it. But she can eat a mouse if she reaches it precisely at the time it ducks underground.

Since all cats are efficient by nature, help Cartesian Cat determine what her minimum initial velocity must be if she hopes to eat all of the mice. Assume that she eats the mice in an optimal order.

Input

The first line of input contains a single positive integer, $n$ (where $1 \le n \le 15$), representing the number of mice. Each of the following $n$ lines describes a mouse given as three space-separated integers $x$, $y$, and $s$. This indicates that a mouse is located at $(x, y)$ and will duck underground at $t = s$ seconds. The values of $x$ and $y$ are in the range $[-1\, 000, 1\, 000]$ and $s$ is in the range $[1,10\, 000]$. No two mice are at the same location. The last line of input contains a single floating-point number, $m$, specified to two decimal places, in the range $[0.75, 0.99]$, representing the multiplicative factor by which the cat slows down after eating a single mouse.

Output

Output the minimum initial velocity (in units per second) necessary for Cartesian Cat to allow her to eat all of the mice, given that she eats them in the optimal order. Your answer should be correct within a relative or absolute error of $10^{-3}$.

1
3 4 2
.75

2.4999999987500003

2
0 100 10
0 -100 100
.80

9.999999999000002

2
0 100 10
0 -100 15
.80

23.33333333177778