Rebel Against the Empire (Large)

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 located on asteroid 0 in a system of N numbered asteroids. Your getaway ship, the Century Quail, is located 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 have elapsed. You escape the instant you jump to asteroid 1.

Asteroid $i$ 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 throughout time; it does not update discretely each second. (An asteroid may 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 happen to occupy the same point at the instant of your jump.

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, there are 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 asteroid $i$ in space, and the distance ($Vx_i$, $Vy_i$, $Vz_i$) it moves in a single second.

Limits

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

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 in order to get away, rounded to exactly 7 digits after the decimal point. The test data guarantees that the rounded value of every answer is unambiguous.

In the first sample test case, we start on a stationary asteroid at (0, 0, 0), and our ship is on an asteroid at (1, 2, 2). There is another asteroid at (1, 1, 1). One option is to jump directly to our ship, which is a distance of 3 away. Another option is to jump to the other asteroid, which is a distance of $\sqrt{3}$ away, and then jump to the ship from there, which is a distance of $\sqrt{2}$ away. The maximum jump distance is 3 for the first option and $\sqrt{3}$ for the second option, so the second option is preferable. In this case the value of S does not matter: all of the asteroids are stationary, so there is no reason to wait around, and all jumps can be made instantaneously.

In the second sample test case, we start on a stationary asteroid at (0, 0, 0). We can wait there for 4 seconds for asteroid 4 to come very close, jump onto it, fly for 1 second on it, and then jump at time 5 back to asteroid 0 (the distance between the two asteroids is 1 at this moment). There we wait 10 seconds, cutting it very close to being caught, and then jump to the speeding asteroid 3 at time 15. Two seconds later, asteroid 3 flies by asteroid 2, and we jump to asteroid 2. At time 27, we can jump from asteroid 2 to asteroid 0. There we patiently wait until time 35 when asteroid 1 reaches us, then we can jump onto it and escape. The longest jump we made was from asteroid 0 to asteroid 3 at time 15, and the distance we jumped was 2.

In the third sample test case, the security forces are really active! You could, of course, wait one second and jump directly to asteroid 1. A better choice, which keeps every jump no longer than 4, is to jump back and forth between asteroids 0 and 2 while waiting for asteroid 1 to get close, and only then jump to it.