Huyendo de los zombis
Estás participando en un concurso de programación celebrado en una facultad alejada de casa. Como los organizadores son previsores, os han dado una planificación de los autobuses de la ciudad, donde se especifica para cada línea por qué paradas pasa y a qué hora. La ciudad está sufriendo en la actualidad una plaga de zombis, por lo que, aunque las paradas de autobuses están rodeadas por una valla que supuestamente te protege de ellos, tú prefieres pasar el menor tiempo posible esperando en una parada (aunque eso haga que el trayecto en autobús hasta tu casa sea más largo de lo necesario). Desafortunadamente, no hay ninguna línea de autobús que pase tanto por la parada de la facultad como por la parada enfrente de tu casa, por lo que por lo menos una vez tendrás que cambiar de autobús.
Ahora que estás algo ocioso mientras tus compañeros de equipo depuran la solución a un problema, quieres calcular la ruta que menor tiempo te hará esperar en las paradas de autobús.
Las rutas de autobuses son siempre circulares y un autobús tarda exactamente una hora en completar la ruta, que repite de forma continua, empezando cada vuelta a las horas en punto. La siguiente figura muestra cuatro líneas de autobús. La primera, por ejemplo, pasa por las paradas con números 1, 2, 3 y 4. Saliendo en punto de la parada 1, pasa a los 20 minutos por la parada 2, a los 40 minutos por la parada 3 y a los 50 minutos por la parada 4 (la figura muestra lo que tarda un autobús en cubrir la distancia entre dos paradas consecutivas). Tras una hora vuelve a pasar por la parada número 1. La línea 2 comienza la ruta en la parada 10, la línea 3 comienza en la parada 8, y la línea 4 comienza en la parada número 7.
Con estas rutas, la mejor forma para ir de la parada número 1 (la facultad) a la parada número 10 (tu casa) consiste en tomar la línea 1 hasta la parada 4, esperar 25 minutos a que pase la línea 2 y llegar al destino (110 minutos después de salir). Si en la parada 4 quisiéramos tomar la línea 3, tendríamos que esperar 40 minutos (tardando en total 100 minutos). Para evitar el riesgo de que los zombis te devoren, es preferible la primera ruta.
Entrada
La entrada consiste en una serie de casos. Para cada caso, primero aparecen en una línea el número N de paradas en la ciudad (numeradas de 1 a N, con 2 ≤ N ≤ 1000) y el número M de líneas de autobús (2 ≤ M ≤ 100). Después aparecen las descripciones de estas líneas, cada una ocupando una línea de texto. Para cada línea aparecen los números de las paradas por las que pasa (el primer número es la parada de comienzo, a las horas en punto) y entre cada par de números el tiempo que el autobús tarda de una parada a la siguiente. Recuerda que todas las líneas tardan una hora en dar la vuelta completa, por lo que el tiempo entre la última parada y la primera se puede calcular a partir de los demás.
Salida
Para cada caso de prueba se escribirá el tiempo mínimo de espera en las paradas de autobús para ir de la parada 1 (la facultad) a la parada N (tu casa). En estas paradas no hace falta esperar porque de la facultad puedes salir cuando pase el autobús que te interesa y al llegar a la parada N entras inmediatamente en tu casa. Puedes suponer que los autobuses cumplen el horario escrupulosamente, que tú tienes un reloj en hora, que los pasajeros suben y bajan de los autobuses instantáneamente (en particular, si dos autobuses paran a la vez en la misma parada, puedes cambiar de uno a otro sin esperar) y que ir caminando entre dos paradas es tan peligroso que ni te lo planteas. Si es imposible llegar a casa desde la facultad, se escribirá Hoy no vuelvo.
Entrada de ejemplo
10 4 1 20 2 20 3 10 4 10 15 4 15 5 10 6 10 7 8 30 4 10 10 7 30 9 3 2 1 30 2 3 30 2 4 2 1 30 3 2 30 4
Salida de ejemplo
25 0 Hoy no vuelvo