Problem
Hay autobuses entre algunos pueblos de la región de Vasyuki. Dado que el tráfico de pasajeros aquí no es muy grande, los autobuses circulan solo unas pocas veces al día.
Maria Ivanovna necesita ir del pueblo d al pueblo v lo más rápido posible (se considera que está en el pueblo d en el momento 0).
Entrada
Primero ingresa el número N – número total de aldeas (1 <= N <= 100), luego los números de pueblo d y v, seguido del número de viajes en autobús R (0 <= R <= 10000). Las siguientes son descripciones de rutas de autobús. Cada vuelo viene dado por el número del pueblo de salida, la hora de salida, el pueblo de destino y la hora de llegada (todos los tiempos son números enteros de 0 a 10000). Si en el momento t un pasajero llega a algún pueblo, entonces puede abandonarlo en cualquier momento a partir de t.
Salida
Imprime el tiempo mínimo en que Maria Ivanovna puede estar en el pueblo v. Si no puede ir de d a v usando las rutas de autobús dadas, imprima -1.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |