제국에 맞선 반란군 (Large)

문제

당신은 사악한 은하 제국에 맞서는 반란군이고, 지금 도망치는 중이다!

당신은 제국의 악의 공장을 파괴했고, 곧 제국 보안군이 뒤쫓아 올 것이다! 공장은 번호가 매겨진 소행성 N개로 이루어진 계에서 0번 소행성에 있다. 탈출선 센추리 퀘일은 1번 소행성에 있고, 그곳에 도착하면 무사히 날아서 달아날 수 있다.

각 소행성은 속도를 가진 공간 속의 한 점이고, 당신은 현재 올라 있는 소행성과 함께 움직인다. 소행성 점퍼를 쓰면 계 안의 어떤 두 소행성 사이든 순간적으로 점프할 수 있다. 긴 점프는 짧은 점프보다 무섭고 우주의 진공은 끔찍하므로, 점프해야 하는 거리의 최댓값을 최소화하려고 한다. 하지만 지금부터 점프하지 않고 연속으로 S초보다 오래 머무르면 제국 보안군에게 잡힌다. 즉 지금부터 첫 점프까지의 시간과 이후 연속한 두 점프 사이의 시간은 모두 S 이하여야 한다. 점프는 아무 순간에나 할 수 있고, 경과 시간이 정수 초일 필요는 없다. 1번 소행성으로 점프하는 순간 탈출에 성공한다.

$i$ 번 소행성은 공간의 위치 ( $x_i$ , $y_i$ , $z_i$ )에서 출발하고, 1초마다 ( $Vx_i$ , $Vy_i$ , $Vz_i$ )만큼 이동한다. 이 이동은 시간에 따라 연속적으로 일어나며, 1초마다 불연속적으로 갱신되지 않는다. (정지한 소행성도 있을 수 있다.) 여러 소행성이 같은 시각에 같은 점에 있어도 아무 일도 일어나지 않는다. 두 소행성 사이는 점프로만 이동할 수 있고, 점프하는 순간 두 소행성이 같은 점에 있더라도 마찬가지다.

최대 점프 거리를 최소화하는 탈출 계획에서, 그 최대 점프 거리는 얼마인가?

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 N(소행성의 수)과 S(점프하지 않고 버틸 수 있는 시간의 한계)가 주어진다. 다음 N개의 줄에는 소행성의 정보가 주어진다. 이 중 $i$ 번째 줄(0부터 센다)에는 여섯 정수가 주어지는데, $i$ 번 소행성의 처음 위치 ( $x_i$ , $y_i$ , $z_i$ )와 1초 동안 이동하는 거리 ( $Vx_i$ , $Vy_i$ , $Vz_i$ )이다.

제한

$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$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 탈출하기 위해 해야 하는 가장 긴 점프의 거리를 소수점 아래 정확히 7자리까지 반올림한 값이다. 모든 테스트 데이터에서 정답은 반올림 결과가 모호하지 않도록 주어진다.

힌트

예제의 첫 번째 테스트 케이스에서는 (0, 0, 0)에 정지한 소행성에서 출발하고, 탈출선은 (1, 2, 2)에 있는 소행성에 있다. (1, 1, 1)에도 소행성이 하나 있다. 탈출선으로 곧바로 점프하는 방법이 있는데, 거리는 3이다. 다른 방법으로 거리가 $\sqrt{3}$ 인 다른 소행성으로 먼저 점프한 뒤, 거기서 거리가 $\sqrt{2}$ 인 탈출선으로 점프할 수 있다. 최대 점프 거리는 첫 번째 방법이 3, 두 번째 방법이 $\sqrt{3}$ 이므로 두 번째 방법이 더 낫다. 이 케이스에서는 모든 소행성이 정지해 있어서 기다릴 이유가 없고 모든 점프를 순간적으로 할 수 있으므로 S 값은 결과에 영향을 주지 않는다.

두 번째 테스트 케이스에서는 (0, 0, 0)에 정지한 소행성에서 출발한다. 4번 소행성이 아주 가까이 올 때까지 4초 동안 기다렸다가 4번 소행성으로 점프하고, 그 위에서 1초 동안 날아간 뒤 시각 5에 0번 소행성으로 돌아온다(이 순간 두 소행성 사이의 거리는 1이다). 그곳에서 잡히기 직전까지 10초를 기다린 뒤, 시각 15에 빠르게 날아가는 3번 소행성으로 점프한다. 2초 뒤 3번 소행성이 2번 소행성 곁을 지나가고, 이때 2번 소행성으로 점프한다. 시각 27에 2번 소행성에서 0번 소행성으로 점프할 수 있다. 그곳에서 1번 소행성이 도착하는 시각 35까지 참을성 있게 기다렸다가 1번 소행성으로 점프해서 탈출한다. 가장 긴 점프는 시각 15에 0번 소행성에서 3번 소행성으로 한 점프이고, 그 거리는 2이다.

세 번째 테스트 케이스에서는 보안군이 정말 활발하게 움직인다! 물론 1초를 기다렸다가 1번 소행성으로 곧바로 점프할 수도 있다. 하지만 1번 소행성이 가까워질 때까지 0번과 2번 소행성 사이를 오가며 점프하다가 그때 1번 소행성으로 점프하면 모든 점프의 거리를 4 이하로 만들 수 있고, 이쪽이 더 좋은 선택이다.