시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Um reino longínquo possui N cidades, dentre as quais K são capitais. O rei Richard quer construir linhas de transmissão, cada uma delas ligando duas cidades. E preciso haver um caminho, ou seja, ´ uma sequência de linhas de transmissão, entre qualquer par de capitais.

Cada linha de transmissão possui um custo associado, que é a distância euclidiana entre as cidades que a linha de transmissão conecta. Como o rei é avarento, ele deseja que as linhas de transmissão sejam criadas de modo que o custo total (soma dos custos das linhas) seja o menor possível.

A figura, na parte A, mostra um exemplo de reino com N = 10 cidades, sendo K = 4 capitais. O engenheiro chefe apresentou ao rei a solução mostrada na parte B, que minimiza de fato o custo total. Mas o rei não gostou de ver uma capital possuindo mais de uma linha de transmissão. Ele, então, determinou uma nova restrição: uma capital só pode estar ligada a uma outra cidade. Desse jeito, depois de trabalhar muito, o engenheiro chefe apresentou a nova solução, ilustrada na parte C da figura. Só que ele não tem certeza se essa solução é ótima e precisa da sua ajuda!

Dadas as coordenadas das cidades, seu programa deve computar o custo total mínimo possível para construir linhas de transmissão de modo que todo par de capitais esteja ligado por um caminho e toda capital esteja ligada a apenas uma cidade.

입력

A primeira linha da entrada contém dois inteiros, N e K, 4 ≤ N ≤ 100 e 3 ≤ K < min(10, N), indicando respectivamente o número de cidades e o número de capitais. As N linhas seguintes contêm, cada uma, dois inteiros X e Y , −1000 ≤ X, Y ≤ 1000, representando as coordenadas de uma cidade. As K primeiras cidades são as capitais. Não há duas cidades com as mesmas coordenadas.

출력

Imprima uma linha contendo um número real, com 5 casas decimais, indicando o custo total mínimo para construir as linhas de transmissão, de acordo com as restrições acima.

예제 입력 1

6 4
-20 10
-20 -10
20 10
20 -10
-10 0
10 0

예제 출력 1

76.56854

예제 입력 2

22 9
-3 -25
0 -6
-1 -9
2 -21
-5 -19
0 -23
-2 24
-4 37
-3 33
-3 -12
2 39
3 -49
-3 -26
2 24
5 3
-4 -9
-2 -9
-4 8
3 -33
-2 31
-1 -13
0 2

예제 출력 2

95.09318