Aplausos
Cuando termina un espectáculo, suena la última palabra del discurso de alguien ilustre o, simplemente, cuando llega la hora, la gente se pone a aplaudir como gesto de admiración o agradecimiento. Tenemos tan interiorizado este acto que es fácil saber cuándo va a ocurrir.
Lo que no es tan fácil es saber en qué momento terminará la ovación (o el abucheo, que también los hay). Depende de la decisión de un numeroso grupo de personas que interactúan entre sí y que pueden mantenerse aplaudiendo más o menos tiempo dependiendo de lo que hagan los demás.
Últimamente he asistido a muchos aplausos colectivos y he llegado a una conclusión. Dependiendo del grado de implicación con el suceso ovacionado, cada persona decide con antelación, de forma individual y subconsciente, el máximo tiempo que se mantendrá aplaudiendo. Ese tiempo se ve recortado si, a su alrededor, el clamor desciende por debajo de un umbral. Al fin y al cabo a muy poca gente le gusta quedarse aplaudiendo sola.
Entrada
Cada caso de prueba comienza con un número 1 ≤ N ≤ 100.000 indicando cuánta gente participa en un aplauso. A continuación aparecen N líneas con dos números, ti y pi describiendo el comportamiento de cada participante. El primero (mayor que 0) indica cuántos segundos está dispuesta la persona i a mantenerse aplaudiendo. Pasado ese tiempo, dejará de hacerlo haga lo que haga el resto. Por su parte, pi (entre 1 y N) indica cuánta gente debe mantenerse aplaudiendo para que la persona i no deje de hacerlo antes de tiempo. En esta cuenta se incluye a sí misma. Si en un determinado instante el número baja de ese valor, la persona i se detendrá inmediatamente.
El procesamiento de la entrada debe terminar al encontrarse un caso sin gente.
Salida
Por cada caso de prueba se indicará el número de segundos que durará el aplauso.
Entrada de ejemplo
1 100 1 2 90 1 40 1 3 40 1 120 2 50 3 3 40 2 40 3 40 1 0
Salida de ejemplo
100 90 40 40