Problema número 692

Choques en el carril bici

Tiempo máximo: 1,000-4,000 sMemoria máxima: 20480 KiB
Carril bici con peatones

Los carriles bici (en algunos sitios conocidos como ciclovías) son carriles destinados a la circulación en exclusiva de bicicletas. Dependiendo de la planificación urbanística y del presupuesto, su calidad puede variar. Por ejemplo, los hay que están pintados con un color distinto para diferenciarlos, hay algunos con una línea central para delimitar los dos sentidos, existen los que disponen de una buena separación entre el carril y la calzada que hay a su lado, etc.

No obstante, todo esto es calidad "sobre el papel". En la práctica los carriles bici más cotizados, los que buscamos todos los aficionados a dar pedales, los carriles soñados por cualquier planificador de urbanismo, los carriles, en definitiva, de mayor calidad son los que, una vez en funcionamiento, están libres de peatones.

En nuestra región hace unos años inauguraron un carril bici que todavía estamos pagando con nuestros impuestos y que sirve para unir los distintos pueblos de la zona. Sobre el papel el diseño del carril era perfecto: vallas a los lados para evitar que los coches pudieran invadirlo, asfalto de calidad y línea discontinua central delimitando los dos carriles, uno por sentido. La pega: está lleno de jubilados dando el paseo. Tanto es así que todos los ciclistas nos agolpamos en uno de los sentidos sin atrevernos a invadir el otro.

Esto provoca situaciones de peligro constantes. Tanto si viene alguien de frente como si vas a mayor velocidad que otro ciclista en tu misma dirección y quieres adelantarle, solo hay dos opciones: o bien te chocas con el ciclista, o bien invades la otra mitad del carril llena de peatones.

Lejos de intentar evitar el problema multando a los viandantes para que dejen de ocupar un espacio que no les corresponde, el ayuntamiento de mi pueblo ha decidido detectar los accidentes con antelación para llegar cuanto antes a socorrer a los heridos. Gracias a las cámaras de seguridad instaladas, conoce en cada momento la posición y velocidad de todos los ciclistas que hay en el tramo del carril que atraviesa el pueblo. La pregunta ahora es saber en qué momento ocurrirá la primera colisión.

Entrada

Cada caso de prueba ocupa dos líneas. La primera contiene un número n con el número total de ciclistas que hay en la sección del carril vigilada (1 ≤ n ≤ 300.000). A continuación aparece una línea con n parejas de números, uno por ciclista. De cada pareja, el primer número representa la posición y el segundo la velocidad del ciclista, ambos enteros.

Las posiciones están medidas con respecto a la plaza del pueblo por la que pasa el carril y pueden ser tanto negativas como positivas aunque el valor absoluto nunca superará 109. Las velocidades también pueden tener ambos signos para representar ambos sentidos y su valor absoluto no supera nunca el millar.

Al último caso le sigue una línea con un 0 que no debe procesarse.

Salida

Por cada caso de prueba se escribirá el momento en el que ocurre la primera colisión. Para evitar problemas de precisión escribiremos únicamente la parte entera. O, definiéndolo formalmente, si la colisión ocurre en el instante t escribiremos el número entero s tal que s ≤ t < s+1.

En caso de no producirse ninguna colisión se escribirá SIN COLISION.

Entrada de ejemplo

2
-2 1 2 -1
2
-2 1 2 1
4
10 -1 -10 1 2 1 2 3
2
1 2 6 -1
0

Salida de ejemplo

2
SIN COLISION
0
1