Cat and Mice

A cat lives on the Cartesian plane and her home is at $(0, 0)$. No mouse lives at that point.

At time $t = 0$, $n$ mice stick their heads above the ground at distinct points, and the cat sees every one of them. Mouse $i$ stays above ground at its point until time $s_i$, then ducks underground where the cat cannot reach it.

The cat plans to eat every mouse. At time $t = 0$ she leaves $(0, 0)$ with initial speed $v$ and runs in a straight line toward one of the mice. She eats it the instant she arrives, then runs in a straight line toward another mouse, and she repeats this until no mouse is left. Eating takes no time.

Every meal slows her down: her speed is multiplied by the constant $m$ each time she eats a mouse, so after eating $k$ mice she moves at speed $v m^k$.

The cat eats mouse $i$ only if she reaches its point at time $s_i$ or earlier. Arriving exactly at time $s_i$ still counts.

The cat picks the order that suits her best. Find the smallest initial speed $v$ for which some order lets her eat all $n$ mice.

The first line contains an integer $n$ ($1 \le n \le 15$), the number of mice.

Each of the next $n$ lines contains three integers $x$, $y$, and $s$ ($-1000 \le x, y \le 1000$, $1 \le s \le 10000$), meaning that a mouse sits at $(x, y)$ and ducks underground at time $t = s$. No two mice share a point, and no mouse is at $(0, 0)$.

The last line contains $m$ ($0.75 \le m \le 0.99$), a decimal number with one or two digits after the decimal point. It may be written without the leading zero, as in .75.

Print the minimum initial speed, in units of distance per second, that lets the cat eat every mouse. Round it to six digits after the decimal point and print exactly six of them.