Espírito Olímpico

Dentre as estratégias de divulgação dos esportes olímpicos, foi elaborado um evento que consiste em uma série de apresentações e palestras com campeões e atletas olímpicos, tendo início com uma cerimônia em estádio fechado, na cidade sede, um ciclo de palestras diárias, uma por cidade membro escolhida, e um encerramento novamente na cidade sede: um show musical com vários artistas.

Entretanto, por conta de restrições orçamentárias, dentre as $N$ cidades escolhidas previamente, o evento poderá contar apenas com $M$ delas, incluindo a cidade sede. Além deste corte, é preciso determinar a melhor sequência de visitas das cidades membro (cada cidade membro deve ser visitada uma única vez, partindo da cidade sede e retornando à sede ao final das visitas), no sentido de caminho mais curto, para reduzir os gastos com transporte dos atletas e locomoção de equipamentos.

Neste contexto, dados os valores de $N$, $M$ e as coordenadas das cidades previamente escolhidas, determine a distância mínima a ser percorrida pela delegação quando consideradas todas as escolhas possíveis para as $M$ cidades que farão parte do evento e exiba os identificadores das cidades (cada cidade recebeu um identificador numérico sequencial, com início em um) que compõem a melhor escolha, em ordem crescente. Caso exista mais de uma escolha ótima possível, exiba a menor delas em ordem lexicográfica.

Entrada

A primeira linha da entrada contém os valores de $N$ ($3\leq N\leq 12$) e $M$ ($3\leq M\leq \min\lbrace N, 6\rbrace$), separados por um espaço em branco.

As $N$ linhas seguintes contém pares de inteiros $x_i$ e $y_i$ ($-1.000\leq x_i, y_i\leq 1.000, 1\leq i\leq N$), separados por um espaço em branco, que correspondem às coordenadas cartesianas, em quilômetros, da localização da $i$-ésima cidade previamente escolhida. A distância entre duas cidades é o comprimento do segmento de reta que une os pontos que identificam ambas cidades (distância euclidiana).

É garantido que todas as cidades estão localizadas em pontos distintos.

Saída

Imprima, em uma linha, a distância mínima a ser percorrida, em quilômetros. Se a distância informada é $x$ e a solução correta é $y$, a distância $x$ será considerada correta se $\frac{|x - y|}{\max\{1, |y|\}} < 10^{-6}$.

Na linha seguinte devem ser impressos os identificadores da escolha de cidades ótima, segundo os critérios descritos anteriormente. Os identificadores devem estar separados por um espaço em branco.

Exemplo de entrada 1

5 3
10 10
30 20
-10 50
-10 -20
40 40

Exemplo de saída 1

87.14776642
1 2 5

Exemplo de entrada 2

4 3
10 10
-10 10
10 -10
-10 -10

Exemplo de saída 2

68.28427125
1 2 3

Exemplo de entrada 3

5 5
363 -746
483 653
-504 -750
-22 -269
-897 -919

Exemplo de saída 3

4835.94076171
1 2 4 3 5