고속도로를 건너는 다리처럼

P-22 이야기가 남긴 유산 중 하나는 캘리포니아가 고속도로 위와 아래에 야생동물 통로를 점점 더 많이 짓고 있다는 것이다. P-22는 긴 여정에서 살아남았고, 이전 문제의 해법도 일부 도움이 되었다. 하지만 다른 많은 산사자는 그러지 못한다. 동물이 고속도로를 무단으로 건너는 대신 이 통로를 이용하도록 익히게 하면 동물의 사망과 교통사고로 인한 사람의 위험이 줄어든다. P-22에게서 직접 영감을 받은 첫 야생동물 통로인 Wallis Annenberg Crossing은 2022년 4월에 착공되었다.

여기서 목표는 동물이 걷는 거리를 최대한 짧게 만들도록 여러 야생동물 통로의 위치를 정하는 것이다. Caltrans와 CDFW의 예산이 지을 수 있는 통로의 수를 정한다. 동물들이 각자 가장 가까운 통로까지 걷는 거리의 평균이 최소가 되도록 통로의 위치를 고른다. 각 동물 i의 위치는 좌표 $(x_i, y_i)$로 주어진다. 고속도로는 $(-\infty, 0)$에서 $(+\infty, 0)$까지 뻗은 무한한 x축으로 모델링한다. 고속도로 위의 $c$개 위치를 골라 통로를 지을 수 있다. 고속도로를 건너야 하는 동물은 먼저 직선으로 고속도로까지 이동한 뒤, 고속도로를 따라 걸어서 지어진 가장 가까운 통로까지 간다.

첫 줄에 데이터 세트의 수 $K$($1 \le K \le 100$)가 주어진다. 각 데이터 세트의 첫 줄에는 두 정수 $c$와 $n$이 주어진다. $c$($1 \le c \le 40$)는 지을 수 있는 통로의 수이고, $n$($1 \le n \le 100$)은 동물의 수이다. 이어지는 $n$개의 줄에는 각 동물의 위치 $x_i$, $y_i$가 부동소수점 수로 주어진다. 값은 -1000000.0 이상 1000000.0 이하이다.

각 데이터 세트마다 한 줄에 "Data Set x:"를 출력한다. 여기서 x는 데이터 세트 번호이다. 그다음 $c$개의 통로를 지어 얻을 수 있는 최소 평균 거리를 출력한다. 이 거리는 모든 동물이 각자 가장 가까운 통로까지 가는 거리의 평균이다. 각 데이터 세트의 출력 뒤에는 빈 줄을 출력한다.