Ir al contenido (saltar navegación)

Abuelos felices

Tiempo máximo: 1,000-2,000 sMemoria máxima: 8192 KiB
Abuelo feliz

Han ido pasando los años y la familia de mis abuelos no ha dejado de crecer. Lo que comenzó siendo una joven pareja recién llegada a la ciudad desde un pequeño pueblecito se ha convertido en una gran familia con un montón de hijos que a su vez se han casado y han tenido su propia descendencia. Y ahora los primos vamos teniendo nuestras parejas lo que hace que seamos todavía más.

Esa gran familia es una gozada en verano cuando organizamos un día de campo en el que toda la tropa, mesas de picnic en mano, nos vemos en algún encinar y disfrutamos de una barbacoa y de juegos al aire libre.

En navidades las cosas son un poco más difíciles porque cualquier casa se queda pequeña para las cenas de nochevieja. Con los años juntarnos las tres generaciones se ha convertido en una misión realmente imposible.

Afortunadamente para los anfitriones, los primos nos hemos ido haciendo mayores y ahora no estamos toda la noche en la casa sino que hacemos otros planes tanto antes de la cena como después. El resultado es que cada uno llegamos y nos vamos a horas distintas. Es raro que coincidamos todos para la cena pero los abuelos están contentos porque esa noche todos pasamos al menos un rato con ellos. Y como no coincidimos todos a la vez, el número de puestos en la mesa (¡y de sillas!) que se necesitan no son tantos.

Entrada

La entrada está compuesta por un número indeterminado de casos de prueba, cada uno ocupando varias líneas.

La primera línea de cada caso de prueba contiene un único número N con la cantidad de comensales que pasaremos por la casa (hasta 100.000). A continuación aparecen N líneas con el instante de llegada y salida de cada uno (números distintos entre 0 y 109).

Tras el último caso de prueba viene una línea con un 0 que no debe procesarse.

Salida

Por cada caso de prueba se escribirá una línea con el número exacto de plazas que se necesitan para que los N comensales podamos permanecer sentados durante todo el tiempo que estamos allí, seguido de la cantidad de tiempo en la que la ocupación de la casa es máxima.

Ten en cuenta que en el mismo momento en el que una persona se va se puede sentar otra.

Entrada de ejemplo

2
0 10
5 15
5
0 20
1 3
15 18
3 5
18 19
0

Salida de ejemplo

2 5
2 8