Like a Bridge over Troubled Freeways

One of the legacies of P-22's story is that California is building more wildlife crossings over and under freeways. P-22 survived his long journey, in part thanks to your solution to the previous problem, but many other mountain lions do not. The idea is that animals will learn to use these crossings instead of running across the freeway, which reduces deaths among them and the risk to humans from traffic accidents. The first wildlife crossing directly inspired by P-22, the Wallis Annenberg Crossing, began construction in April 2022.

Here, your goal is to decide where to build several wildlife crossings so that animals walk as little as possible. The budget of Caltrans and CDFW determines how many crossings you can build. You should choose their locations to minimize the average distance animals walk to their closest crossings. Each animal i lives at coordinates $(x_i, y_i)$. The freeway is modeled as the infinite x-axis, going from $(-\infty, 0)$ to $(+\infty, 0)$. You can choose $c$ locations on the freeway for your crossings. An animal that needs to cross the freeway first walks in a straight line to the freeway, then walks along the freeway to the closest crossing you have built.

The first line contains $K$ ($1 \le K \le 100$), the number of data sets. Each data set begins with a line containing two integers $c$ and $n$, where $1 \le c \le 40$ is the number of crossings you can build and $1 \le n \le 100$ is the number of animals. The next $n$ lines each give the location $x_i$, $y_i$ of an animal as a floating point number between $-1000000.0$ and $1000000.0$.

For each data set, print "Data Set x:" on a line by itself, where x is the data set number. Then print the minimum average distance from all animals to their respective closest crossings that you can achieve by building $c$ crossings. Print a blank line after each data set.