Water Main Break, Fixed

Interview

Time limit8sMemory limit128 MB

Summary

A crew starts at the origin and must visit up to 10 breaks in some order; pick the order that minimizes total water lost, where each break waits until its start time.

Level: Medium6 of 10
Topics: Brute force, Greedy, Simulation, Geometry
Solved: No attempts yet

Problem

The reason a water main break wastes so much water is that repairs usually take a while, and much of that time is spent just getting a repair crew to the break. This matters most when several pipes burst at once and there are not enough crews to fix them all simultaneously. You then have to decide whether to first drive to a distant break that may be leaking heavily, or to quickly patch a few nearby ones. That is a non-trivial optimization problem, and it is exactly the one you are asked to solve here.

You are given a list of water main breaks. Each break has coordinates $(x, y)$ , the time $t$ at which it starts flooding, and the rate $r$ at which water flows out of it. A single repair crew starts at the origin $(0, 0)$ at time $0$ and travels along straight lines at a given speed $v$ (there are no streets or obstacles). Your goal is to pick a visiting order that minimizes the total amount of water lost.

The water lost at a break equals $r \times (\text{repair time} - t)$ , where the repair time is the moment the crew reaches that break. Repairs are instantaneous, so the crew can immediately drive on. The crew knows the entire future, but if a break starts at time $3$ , arriving at time $2.5$ does not help: the crew must wait until time $3$ to repair it, in which case that break loses no water.

Input

The first line contains the number of data sets $K$ , followed by the $K$ data sets, each in the following form.

The first line of a data set contains an integer $n$ ( $1 \le n \le 10$ ), the number of water main breaks, and a real number $v > 0$ , the speed of the repair crew's truck.

Each of the next $n$ lines describes one break with four real numbers $x_i,\ y_i,\ t_i,\ r_i$ . The location $(x_i, y_i)$ satisfies $-1000.0 \le x_i, y_i \le 1000.0$ , $0 \le t_i \le 1000.0$ is the time at which the pipe there broke, and $0 \le r_i \le 1000.0$ is the rate at which water flows out. Once the crew reaches a break, the repair is instantaneous and it can immediately drive to the next location.

Output

For each data set, output Data Set x: on a line by itself, where $x$ is the data set's number, starting from $1$ .

On the next line, output the minimum total amount of water lost when the crew visits the breaks in the optimal order, rounded to two decimals. The crew starts at the origin $(0, 0)$ at time $0$ .

Separate consecutive data sets with a single blank line.

Examples6

Example 1

Input

2
1 2
6 0 0 1
5 1.0
3.2 0 0 10
-4 -3 6 1000
0 0 15 0.1
0 1 17 0.01
0 -2 17 0.015

Expected output

Data Set 1:
3.00

Data Set 2:
138.27

Example 2
Input
```
1
1 1
3 4 0 2
```
Expected output
```
Data Set 1:
10.00
```
Example 3
Input
```
1
1 10
1 0 100 5
```
Expected output
```
Data Set 1:
0.00
```

Example 4

Input

Expected output

Data Set 1:
111.05

Example 5

Input

Expected output

Data Set 1:
0.00

Example 6

Input

1
2 1
5 0 0 10
5 0.01 100 1000

Expected output

Data Set 1:
50.00