Ahorrando fuerzas
Como bien quedó reflejado en la película Regreso al Futuro, los usuarios de monopatines muchas veces terminan cediendo a la comodidad de agarrarse a algún vehículo motorizado y utilizar su fuerza tractora para desplazarse sin cansarse. Si el trayecto transcurre por una carretera sin desvíos la situación es perfecta porque cualquier coche que se utilice te llevará al punto de destino.
Aunque no aparece explícitamente en la película, podemos adivinar que eso es precisamente lo que le ocurre a su protagonista, Marty McFly. Para ir al instituto tiene que recorrer dos millas por carretera hasta el pueblo de Hill Valley. Lo que hace es ponerse al principio de la carretera y esperar al primer coche que pase y engancharse a él. Cada vez que algún vehículo que va más rápido les adelanta, se suelta y se cambia para llegar antes.
Queremos saber a qué hora llegará Marty al final del trayecto. Sabemos que todos los vehículos que van por esa carretera se mueven a velocidad constante y conocemos en qué momento pasa cada uno por el punto de inicio del recorrido. Por comodidad todos esos instantes se dan en base al momento en el que Marty se pone a esperar un vehículo al que agarrarse.
Entrada
La entrada está compuesta por varios casos de prueba, cada uno ocupando dos líneas.
La primera línea de cada caso de prueba contiene dos números: el primero es la longitud del trayecto que hay que recorrer (entre 1 y 1.000.000) y la segunda el número n de vehículos que pasan por la carretera ese día (1 ≤ n ≤ 50.000).
La segunda línea contiene n parejas de números, una por cada vehículo. El primer valor de la pareja es el instante de tiempo en el que pasa por delante del punto de inicio del recorrido de Marty (su valor absoluto no supera el millón) y el segundo la velocidad que mantiene durante todo el recorrido. El límite de velocidad de la carretera es 100.
Salida
Por cada caso de prueba se escribirá una única línea indicando el instante de tiempo en el que Marty llegará al destino. Aunque el resultado puede ser un número real, se escribirá únicamente la parte entera.
Se garantiza que siempre habrá al menos un vehículo que le permita completar su recorrido.
Entrada de ejemplo
10 2 0 5 -10 2 10 2 0 2 2 10 10 1 0 3
Salida de ejemplo
2 3 3