All your base are belong to us

시간 제한2초메모리 제한512 MB

요약

평면 위 임의의 점을 골라 가장 먼 K개 기지까지의 거리 합이 최소가 되게 하고, 그 최솟값을 출력한다.

난이도: 어려움10점 중 8점
유형: 기하, 이분 탐색, 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

서기 2101년, 전쟁이 시작되었다. 적이 우리의 모든 기지를 점령했다. 기지를 되찾기 위해 우리는 본부를 세우기로 했다. 모든 기지가 본부에서 그리 멀지 않도록 본부의 위치를 정해야 한다. 그래서 본부에서 가장 먼 $K$ 개의 기지까지의 거리의 합이 최소가 되도록 위치를 정하기로 했다. 기지들은 2차원 평면 위에 있고, 본부는 격자점이 아니더라도 이 평면 위 임의의 장소에 세울 수 있다.

주어진 기지의 위치로부터 최적의 본부 위치를 구하는 것이 당신의 임무다.

입력

입력의 첫째 줄에는 두 정수 $N$ 과 $K$ 가 주어진다. 정수 $N$ 은 기지의 개수이다( $1 \le N \le 200$ ). 정수 $K$ 는 계산에 고려할 기지의 개수이다( $1 \le K \le N$ ). 다음 $N$ 개의 줄 각각에는 두 정수 $x$ 와 $y$ 가 주어지며, 이는 각 기지의 좌표이다. 주어지는 좌표의 절댓값은 모두 1000 이하, 즉 $-1000 \le x_i,y_i \le 1000$ 을 만족한다.

출력

본부에서 가장 먼 $K$ 개의 기지까지의 거리의 합의 최솟값을 출력한다. 출력은 절대 오차 또는 상대 오차가 $10^{-3}$ 이하여야 한다.

예제3

예제 1
입력
```
3 1
0 1
1 0
1 1
```
예상 출력
```
0.70711
```
예제 2
입력
```
6 3
1 1
2 1
3 2
5 3
8 5
13 8
```
예상 출력
```
17.50426
```

예제 3

입력

예상 출력

1841.20904