Problem
Uno de los equipos que participan en la Olimpiada decidió regresar a casa en tren. Al mismo tiempo, los chicos quieren llegar a casa lo antes posible. Desafortunadamente, no todos los trenes eléctricos van desde la ciudad donde se lleva a cabo la Olimpiada hasta la estación donde viven los muchachos. Y, lo que es aún más ofensivo, no todos los trenes eléctricos que pasan por su estación paran en ella (así como en general, los trenes eléctricos no paran en todas las estaciones por las que pasan).
Todas las estaciones de la línea están numeradas del 1 al N. Al mismo tiempo, la estación número 1 se encuentra en la ciudad donde se lleva a cabo la Olimpiada, y en el momento 0 los muchachos llegan a la estación. La estación a la que deben llegar los muchachos tiene el número E.
Escriba un programa que, dado un horario de tren, calcule el tiempo mínimo en que los muchachos pueden estar en casa.
Entrada
En el archivo de entrada los números N (2 ≤ N ≤ 100) y E (2 ≤ E ≤ N) se escriben primero. Luego se escribe el número M (0 ≤ M ≤ 100), que indica el número de recorridos del tren. La siguiente es una descripción de M viajes de trenes eléctricos. La descripción de cada vuelo de tren comienza con el número Ki (2 ≤ Ki ≤ N) — el número de estaciones en las que se detiene, seguido de Ki pares de números, el primer número de cada par especifica el número de la estación, el segundo — hora en que el tren se detiene en esta estación (la hora se expresa como un número entero de 0 a 109). Las estaciones dentro del mismo vuelo se ordenan en orden ascendente de tiempo. Durante un viaje, el tren se mueve en la misma dirección todo el tiempo; ya sea lejos de la ciudad o hacia la ciudad.
Salida
Al archivo de salida imprimir un número — el tiempo mínimo en que los muchachos pueden estar en su puesto. Si no pueden llegar allí por las rutas de tren existentes, escriba en letra de imprenta: 1.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |