Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

El vendedor viajero (traveling salesman) llega al reino de Lazyland. Él planea comenzar en la capital, visitar cada ciudad y luego retornar a la capital. Él conoce las coordenadas de cada ciudad, pero no se han construido caminos aún. Es obvio que no es posible visitar todos los destinos si alguna ciudad no está conectada a todas las otras.

Asume que existen $n$ ciudades. Sus coordenadas son $(x_1, y_1 ), ..., (x_n, y_n)$, y $(x_1, y_1)$ es la capital. El rey quiere ayudar al viajero. Por ello, ordenó construir los caminos para el viajero. No obstante, las personas en el reino son muy perezosas.

Debido a que los ingenieros son perezosos, ellos solo pueden construir caminos entre dos ciudades $(x_i, y_i)$ y $(x_j, y_j)$ usando segmentos horizontales y verticales. Por lo tanto la longitud del camino será $|x_i - x_j| + |y_i - y_j|$.

Debido a que los trabajadores son muy perezosos también, ellos no construirán más de $n - 1$ caminos para el viajero — ellos escucharon que $n - 1$ caminos son suficiente para conectar todos los destinos. Nota que el vendedor solo cambia de caminos en las ciudades.

El vendedor puede seleccionar los caminos a construir. Puedes decirle al vendedor cuál es la longitud de la ruta más corta que puede usar para visitar cada ciudad y regresar a la capital ?

Input

Output

Sample test(s)