제국에 맞선 반란군

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

당신은 제국의 악의 공장을 파괴했고, 곧 제국 보안군이 당신을 추격할 것이다! 공장은 번호가 매겨진 N개의 소행성으로 이루어진 항성계의 소행성 0에 있다. 탈출선 Century Quail은 소행성 1에 있으며, 그곳에 도착하면 안전하게 날아가 탈출할 수 있다.

각 소행성은 속도를 지닌 우주의 한 점이며, 당신은 현재 올라타고 있는 소행성과 함께 우주 공간을 이동한다. Asteroid Jumper를 사용하면 항성계에 있는 임의의 두 소행성 사이를 순간적으로 도약할 수 있다. 긴 도약은 짧은 도약보다 더 무섭고 우주의 진공은 끔찍하므로, 필요한 도약 거리의 최댓값을 최소화하려 한다. 하지만 지금부터 도약하지 않은 채 연속으로 S초를 초과해 보내는 일이 한 번이라도 있으면 제국 보안군에게 붙잡힌다. 즉, 지금부터 첫 도약까지의 시간 간격과 이후의 각 도약 사이의 시간 간격은 S 이하여야 한다. 어느 순간에든 도약할 수 있으며, 정수 초만큼 시간이 흐른 뒤일 필요는 없다. 소행성 1로 도약하는 순간 탈출한다.

i번째 소행성은 우주 공간의 위치 ($x_{i}$, $y_{i}$, $z_{i}$)에서 출발하며, 매초 총 ($V_{xi}$, $V_{yi}$, $V_{zi}$)의 거리를 이동한다. 이 이동은 시간의 흐름 내내 연속적이며, 매초 이산적으로 갱신되지 않는다. (소행성이 정지해 있을 수도 있다.) 여러 소행성이 같은 시각에 우주의 같은 점을 차지해도 아무 일도 일어나지 않는다. 도약하는 순간 두 소행성이 같은 점을 차지하더라도, 두 소행성 사이를 이동하려면 반드시 도약해야 한다.

도약 거리의 최댓값을 최소화하는 탈출 계획에서 그 최대 도약 거리는 얼마인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 20. 2 ≤ N ≤ 1000. 1 ≤ S ≤ 100. -500 ≤ $x_{i}$ ≤ 500. -500 ≤ $y_{i}$ ≤ 500. -500 ≤ $z_{i}$ ≤ 500.

작은 데이터 세트 (테스트 세트 1 - 공개)

$V_{xi}$ = 0. $V_{yi}$ = 0. $V_{zi}$ = 0.

큰 데이터 세트 (테스트 세트 2 - 비공개)

-500 ≤ $V_{xi}$ ≤ 500. -500 ≤ $V_{yi}$ ≤ 500. -500 ≤ $V_{zi}$ ≤ 500.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 N(소행성의 수)과 S(도약하지 않고 지낼 수 있는 시간의 제한)가 주어진다. 다음 N개 줄에는 소행성에 대한 설명이 주어진다. 이 중 i번째 줄은 0부터 세었을 때, 여섯 개의 정수, 즉 i번째 소행성의 우주 공간 내 초기 위치 ($x_{i}$, $y_{i}$, $z_{i}$)와 한 초 동안 이동하는 거리 ( $V_{xi}$, $V_{yi}$, $V_{zi}$)를 담고 있다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 탈출하기 위해 해야 하는 도약 중 가장 긴 도약의 거리를 나타내는 부동소수점 수이다. y은 정답과의 절대 오차 또는 상대 오차가 10^{-4} 이내이면 정답으로 간주된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참고하라.

예제 케이스 #1은 작은 데이터 세트에 나올 수 있는 유일한 예제 케이스이다. 큰 데이터 세트에는 어느 예제 케이스든 나올 수 있다.

예제 케이스 #1에서 우리는 (0, 0, 0)에 있는 정지한 소행성에서 출발하며, 탈출선은 (1, 2, 2)에 있는 소행성에 있다. 또 다른 소행성 하나가 (1, 1, 1)에 있다. 한 가지 방법은 3의 거리만큼 떨어진 탈출선으로 곧장 도약하는 것이다. 다른 방법은 sqrt(3)의 거리만큼 떨어진 다른 소행성으로 도약한 다음, 그곳에서 sqrt(2)의 거리만큼 떨어진 탈출선으로 도약하는 것이다. 첫 번째 방법의 최대 도약 거리는 3이고 두 번째 방법의 최대 도약 거리는 sqrt(3)이므로, 두 번째 방법이 더 낫다.

작은 데이터 세트에서는 S의 값이 중요하지 않다는 점에 유의하라. 모든 소행성이 정지해 있으므로 기다릴 이유가 없으며, 모든 도약을 순간적으로 할 수 있다.

예제 케이스 #2에서 우리는 (0, 0, 0)에 있는 정지한 소행성에서 출발한다. 그곳에서 소행성 4이 아주 가까이 올 때까지 4초 동안 기다린 뒤 그 소행성으로 도약하고, 그 소행성을 타고 1초 동안 이동한 다음, 시각 5에 소행성 0으로 다시 도약할 수 있다(이 순간 두 소행성 사이의 거리는 1이다). 그곳에서 붙잡히기 직전까지 10초 동안 기다린 다음, 시각 15에 빠르게 움직이는 소행성 3로 도약한다. 두 초 뒤 소행성 3이 소행성 2 옆을 지나가면 소행성 2로 도약한다. 시각 27에는 소행성 2에서 소행성 0으로 도약할 수 있다. 그곳에서 소행성 1이 우리에게 도달하는 시각 35까지 끈기 있게 기다린 다음, 그 소행성으로 도약하여 탈출할 수 있다. 우리가 한 가장 긴 도약은 시각 15에 소행성 0에서 소행성 3으로 한 도약이며, 그 거리는 2이다.

예제 케이스 #3에서는 보안군이 정말 활발하게 움직인다! 물론 한 초 동안 기다렸다가 소행성 1로 곧장 도약할 수도 있지만, 더 나은 선택은 소행성 1이 가까워질 때까지 기다리는 동안 소행성 0과 2 사이를 오간 뒤, 그때서야 그 소행성으로 도약하는 것이다. 이 방법을 사용하면 길이가 4를 초과하지 않는 도약만 할 수 있다.