Programando el vídeo P39417

El profesor Oak es un gran seguidor de Humor Amarillo. Tanto, que se ha comprado una antena de satélite para ver el programa en varias cadenas europeas. El profesor Oak también tiene una guía de todos los canales de Europa, y quiere programar su vídeo para grabar cada día tantos episodios como sea posible. Pero no es tan fácil: el vídeo sólo puede grabar un canal a la vez. Además, los capítulos pueden tenir distintas duraciones (el modo en que están editados, la publicidad intercalada, etcétera).

Te pedimos que ayudes al profesor Oak. Haz un programa que, dado los minutos de inicio y de final de emisión de todos los episodios de Humor Amarillo en todos los canales europeos durante varios días, calcule y escriba el número máximo de episodios que puedan grabarse cada día. El aparato grabador necesita unos pocos segundos para parar la grabación y iniciar otra, por lo que no es posible grabar dos programas si uno de ellos empieza justo en el instante en el que acaba el otro.

Entrada

La entrada consiste en diversos casos. Cada caso tiene un natural n≥ 1, seguido de n pares (i₁, f₁), (i₂, f₂), …, (i_n, f_n) de naturales que indiquen el minuto de inicio y el minuto de final (ambos inclusive) de cada capítulo de un día. Para todo j entre 1 y n se cumple 0 ≤ i_j ≤ f_j < 1440.

Salida

Para cada caso de entrada, escribe una línea con el número máximo de capítulos que el profesor Oak podrá grabar aquel día.

Puntuación

• Test1:  ‍10 Puntos ‍

  Resolver una entrada con no más de 500 casos de n≤ 5.

• Test2:  ‍10 Puntos ‍

  Resolver una entrada con no más de 500 casos de n≤ 10.

• Test3:  ‍10 Puntos ‍

  Resolver una entrada con no más de 500 casos de n≤ 20.

• Test4:  ‍10 Puntos ‍

  Resolver una entrada con no más de 500 casos de n≤ 50.

• Test5:  ‍10 Puntos ‍

  Resolver una entrada con no más de 500 casos de n≤ 100.

• Test6:  ‍10 Puntos ‍

  Resolver una entrada con no más de 20 casos de n≤ 500.

• Test7:  ‍10 Puntos ‍

  Resolver una entrada con no más de 20 casos de n≤ 1000.

• Test8:  ‍10 Puntos ‍

  Resolver una entrada con no más de 10 casos de n≤ 10000.

• Test9:  ‍20 Puntos ‍

  Resolver una entrada con no más de 3 casos de n≤ 100000.