수도관 파열 (개정판)

수도관이 파열되면 물이 크게 낭비되는 이유는 대개 수리에 시간이 걸리기 때문입니다. 그 시간의 상당 부분은 수리반이 파열 지점까지 이동하는 데 쓰입니다. 특히 여러 곳이 동시에 터졌는데 이를 한꺼번에 처리할 수리반이 부족할 때 문제가 됩니다. 이때는 물이 더 많이 새는 먼 지점을 먼저 갈지, 가까이 있어 빨리 처리할 수 있는 몇 곳을 먼저 고칠지 결정해야 합니다. 이는 자명하지 않은 최적화 문제이며, 바로 그 문제를 여기서 풀게 됩니다.

파열 지점의 목록이 주어집니다. 각 지점마다 좌표 $(x, y)$, 물이 새기 시작하는 시각 $t$, 그리고 물이 흐르는 속도(유량) $r$ 가 주어집니다. 수리반은 시각 $0$ 에 원점 $(0, 0)$ 에서 출발하며, 주어진 속도 $v$ 로 직선을 따라 이동합니다(도로나 장애물은 없습니다). 목표는 방문 순서를 정하여 손실되는 물의 총량을 최소로 만드는 것입니다.

한 파열 지점에서 손실되는 물의 양은 $r \times (\text{수리 시각} - t)$ 이며, 수리 시각은 수리반이 그 지점에 도착하는 시각입니다. 수리는 즉시 끝나고 곧바로 다음 지점으로 출발할 수 있습니다. 수리반은 모든 파열의 미래 정보를 알고 있지만, 어떤 지점이 시각 $3$ 에 터진다면 시각 $2.5$ 에 그곳에 도착해도 소용이 없습니다. 시각 $3$ 이 될 때까지 기다렸다가 수리해야 하며, 이 경우 그 지점의 손실은 $0$ 입니다.

첫 줄에는 데이터 집합의 개수 $K$ 가 주어지고, 이어서 $K$ 개의 데이터 집합이 다음 형식으로 주어집니다.

각 데이터 집합의 첫 줄에는 파열 지점의 수를 나타내는 정수 $n$ ($1 \le n \le 10$) 과 수리반 트럭의 속도를 나타내는 실수 $v > 0$ 이 주어집니다.

이어지는 $n$ 개의 줄에는 각각 하나의 파열 지점을 설명하는 네 실수 $x_i,\ y_i,\ t_i,\ r_i$ 가 주어집니다. $(x_i, y_i)$ 는 파열 지점의 좌표로 $-1000.0 \le x_i, y_i \le 1000.0$ 이고, $0 \le t_i \le 1000.0$ 은 그곳의 관이 터진 시각, $0 \le r_i \le 1000.0$ 은 물이 흐르는 속도입니다. 수리반이 파열 지점에 도착하면 즉시 수리가 끝나 곧바로 다음 지점으로 이동할 수 있다고 가정합니다.

각 데이터 집합에 대해, 한 줄에 Data Set x: 를 출력합니다. 여기서 $x$ 는 그 데이터 집합의 번호이며 $1$ 부터 시작합니다.

다음 줄에는 수리반이 최적의 순서로 파열 지점들을 방문했을 때 손실되는 물의 최소 총량을 소수점 아래 둘째 자리까지 반올림하여 출력합니다. 수리반은 시각 $0$ 에 원점 $(0, 0)$ 에서 출발합니다.

연속한 데이터 집합 사이는 빈 줄 하나로 구분합니다.