Clúster de microondas
Ante los retrasos continuos en la hora de llegada de los alumnos, los profesores que dan clase a primera hora de la tarde de cierta Facultad han decidido tomar medidas y no dejar entrar a nadie que llegue más de cinco minutos tarde. ¡Se acabaron las interrupciones!
Desde Delegación de Alumnos han contraatacado, culpando al Decanato de la situación. A medio día, argumentan, se forman unas grandes colas en los microondas disponibles para uso libre, lo que hace que haya que esperar mucho tiempo hasta conseguir tener la comida caliente. Y con lo aburridas que son algunas clases, aseguran, no todas las asignaturas se merecen renunciar por ellas a comer los macarrones calientes.
Antes de que llegue la sangre al río ante semejantes comentarios, desde Decanato han pensado que igual habría que hacer una ampliación de hardware en el clúster de microondas de la Facultad para evitar males mayores. Desde Asuntos Económicos miran con preocupación la medida, de modo que han pedido que se haga un estudio del número de microondas que se necesitaría tener disponibles para mantener la espera de sus usuarios dentro de unos márgenes razonables.
Y el Decanato ha querido involucrar a Delegación en él, para evitar críticas futuras… y les ha pedido que hagan ellos la estimación.
Entrada
El programa deberá leer de la entrada estándar múltiples casos de prueba.
Cada uno comienza con dos números enteros, n y t, indicando respectivamente cuánta gente utiliza los microondas a lo largo de un día cualquiera (como mucho 50.000), y cuál es el tiempo de espera máximo permitido.
Después aparecerá una línea con n parejas de números, una por cada hambriento usuario. El primer número de cada pareja indica el instante de tiempo en el que llega a hacer uso de un microondas, y el segundo el tiempo total (mayor que 0) que tiene que utilizarlo para calentar completamente su comida. Los usuarios estarán ordenados por orden de llegada. Hay veces que llegan en grupo, por lo que tendrán el mismo instante de llegada; en ese caso usarán los microondas en el orden en el que aparecen en la entrada.
La entrada terminará con un caso, que no deberá procesarse, en el que no hay nadie que quiera usar los microondas (n = 0).
Por simplicidad, los tiempos son números naturales carentes de unidad.
Salida
Por cada caso de prueba se escribirá el mínimo número de microondas que tiene que haber en el clúster para que nadie espere más tiempo del máximo permitido antes de empezar a calentar su comida. Se asume que hay "fila única", y en cuanto un microondas queda libre (sea cual sea), la siguiente persona en la cola comienza a utilizarlo sin dilación en un tiempo despreciable.
Entrada de ejemplo
2 5 0 5 0 3 3 5 0 6 0 3 10 4 0 0
Salida de ejemplo
1 2