Yincana 2015
En la zona residencial de Concursolandia organizan una yincana todos los años. Los concursantes, por parejas, recorren en orden una serie de puntos, repartidos por la urbanización, donde jueces que velan por el buen funcionamiento del concurso plantean una serie de acertijos a los concursantes, según van llegando. Como en muchas yincanas, los acertijos están encadenados: es imposible acertar uno si no se han recogido las pistas proporcionadas al resolver los acertijos planteados en todos los puntos anteriores (con un número menor).
El complejo residencial está formado por una serie de parcelas muy bien alineadas y separadas mediante avenidas horizontales (de este a oeste) o calles verticales (de norte a sur), como muestra el dibujo. Los puestos de control (círculos rojos) se encuentran en intersecciones entre calles. Los concursantes, que comienzan en la esquina inferior izquierda de la urbanización con pistas para resolver el primer acertijo, para alcanzar un punto tienen que caminar por estas calles, de la forma en la que decidan, pero no pueden atravesar por medio de parcelas. Los concursantes, para no perturbar en exceso a los vecinos, siempre van a la misma velocidad y tardan exactamente 1 minuto en ir de una intersección a la siguiente en horizontal o vertical. Gana el concurso el equipo que menos tiempo emplee en resolver todos los acertijos.
Mica y Dina forman pareja, pero tienen claro que ir siempre juntas les perjudica, y que podrían ganar tiempo si cada una sigue una ruta distinta, comunicándose por móvil las pistas según las vayan recibiendo para que la otra pueda avanzar. Al proponérselo a los jueces, estos no tienen claro si supone demasiada ventaja o si de permitirlo se llenaría el barrio de chicos pululando, por lo que imponen una restricción más: si optan por separarse, en todo momento solamente una de ellas podrá estar caminando y la otra deberá estar parada en un punto de control (o en el comienzo).
¿Cuál es el menor tiempo que necesitan Mica y Dina para resolver todos los acertijos respetando todas estas restricciones?
Entrada
La entrada comienza con un entero que indica el número de casos de prueba que vendrán a continuación. Cada caso comienza con el número N (entre 1 y 500) de puntos de control que forman la yincana. A continuación aparecen N líneas cada una con dos enteros que indican la avenida y la calle en los que se encuentran cada uno de estos puntos, en el orden en el que deben ser visitados. Todos los puntos están en intersecciones diferentes, y ninguno está en el punto de salida. Tanto las avenidas como las calles están numeradas desde 0 hasta 10.000. Los concursantes parten siempre de la intersección (0,0), pero este punto no se contabiliza dentro de los N a visitar.
Salida
Para cada caso de prueba se escribirá el mínimo tiempo necesario para ganar la yincana, si se compite por parejas y se siguen las restricciones impuestas por los jueces.
Entrada de ejemplo
2 6 4 5 2 6 3 1 1 4 5 3 3 8 2 4 4 6 6
Salida de ejemplo
29 12