Rebel Against The Empire (Small)

You are a rebel against the evil Galactic Empire, and you are on the run!

You have sabotaged the Empire's Factory of Evil, and imperial security forces will be after you soon. The factory is on asteroid 0 in a system of $N$ numbered asteroids. Your getaway ship, the Century Quail, is on asteroid 1, and if you can get there, you will be able to fly away safely.

Each asteroid is a single point in space with a velocity, and you move through space along with whichever asteroid you are currently on. Your Asteroid Jumper lets you jump instantaneously between any two asteroids in the system. Long jumps are scarier than short ones (and the vacuum of space is terrifying), so you want to minimize the maximum distance you need to jump. However, starting now, if you ever spend more than a continuous $S$ seconds without jumping, the imperial security forces will catch you. That is, the interval from now until your first jump, and each interval between subsequent jumps, must be less than or equal to $S$. You may jump at any instant; it does not have to be after an integer number of seconds. You escape the instant you jump to asteroid 1.

The $i$-th asteroid starts at position $(x_i, y_i, z_i)$ in space, and it moves a total distance of $(Vx_i, Vy_i, Vz_i)$ each second. This movement is continuous in time; it does not update discretely once per second. (An asteroid can also be stationary.) Nothing happens if asteroids occupy the same point in space at the same time. You can only travel between two asteroids by jumping, even if they occupy the same point at the instant of your jump.

In this version (Small), every asteroid is stationary.

In the escape plan that minimizes the maximum jump distance, what is that maximum jump distance?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains two integers: $N$ (the number of asteroids) and $S$ (the limit on how long you can go without jumping). Next come $N$ lines describing the asteroids. The $i$-th of these lines (counting from 0) contains six integers: the initial position $(x_i, y_i, z_i)$ of the $i$-th asteroid, and the distance $(Vx_i, Vy_i, Vz_i)$ it moves in one second.

Limits

• $1 \le T \le 20$
• $2 \le N \le 1000$
• $1 \le S \le 100$
• $-500 \le x_i \le 500$
• $-500 \le y_i \le 500$
• $-500 \le z_i \le 500$
• $Vx_i = 0$
• $Vy_i = 0$
• $Vz_i = 0$

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the distance of the longest jump you have to make to get away.

Print y rounded to exactly 7 digits after the decimal point. The exact value is always the square root of an integer, so the rounded result is unique.

In the sample, you start on a stationary asteroid at $(0, 0, 0)$, and your ship is on an asteroid at $(1, 2, 2)$. Another asteroid is at $(1, 1, 1)$. One option is to jump directly to your ship, a distance of 3. Another option is to jump to the other asteroid, a distance of $\sqrt{3}$, and then jump from there to the ship, a distance of $\sqrt{2}$. The maximum jump distance is 3 for the first option and $\sqrt{3}$ for the second, so the second option is better.

In this version, the value of S does not matter. Since all asteroids are stationary, there is no reason to wait, and you can make all jumps instantaneously.