El Club de Programación Competitiva de la carrera de Informática ha organizado un Concurso de Programación, y a ti se te a encomendado la tarea de formar los equipos de pruebas para dicho concurso.

Hay $2 ∗ n$ estudiantes interesados en participar(ya se inscribieron) y hay que formar $n$ equipos, cada equipo formado por dos miembros. Dado que los miembros tienen que practicar juntos, todos los estudiantes quieren que la casa de sus miembros esté lo más cerca posible. Sea $d_{1}$ la distancia entre las casas del grupo 1, $d_{2}$ la distancia entre las casas del grupo 2 y así sucesivamente. Debe asegurarse de que la suma ($d_{1} + d_{2} + d_{3} +... + d_{n}$) sea lo mas mínimo posible.

La entrada consiste en múltiples casos de prueba. Cada caso comienza con un número entero $n$ ($1 \leq n \leq 8$). Las siguientes $2 ∗ n$ líneas darán la información de los estudiantes. Cada línea comienza con el nombre del estudiante, seguido de la coordenada $x$ luego la coordenada $y$. Tanto $x$, $y$ son números enteros en el rango de $0$ a $1000$. El nombre de los estudiantes constará únicamente de letras minúsculas y la longitud será como máximo de $20$.
La entrada termina en un caso en el que $n$ es igual a $0$.

Para cada caso, envíe el número de caso seguido de la suma de las distancias, redondeado a 2 decimales de precisión.