iPeds P97568

El nuevo gadget se llama iPed: los consumidores se lanzan desesperados a conseguirlo, y la fábrica de China que los produce no da abasto. Tan pronto tienen las cuatros piezas necesarias para montar un iPed (la Carcasa, la Pantalla, la Batería y el Microcontrolador), uno de sus empleados ensambla el iPed resultante sin perder ni un solo segundo de tiempo.

Sabiendo cuándo llegan las distintas remesas de componentes a la fábrica, escribe un programa que calcule el número de iPeds que podrán fabricarse, y cuándo estarán disponibles.

Entrada

La primera línea de la entrada contiene el número n de remesas que recibe la fábrica, seguido de una cantidad arbitraria de líneas con las n remesas (pueden haber varias remesas en la misma línea). Cada remesa es un triplete de valores con el instante t≥ 0 en el que llega la remesa, el número de componentes m>0 que contiene, y el tipo (C, P, B y M) de los mismos.

Salida

Siempre que sea posible ensamblar un nuevo iPed, escribe una línea con el instante t y el número total de nuevos iPeds que puedan ensamblarse en ese instante. Escribe las líneas en orden cronológico, y no escribas dos líneas con el mismo valor instante t.

Puntuación

• Test1:  30 Puntos 

  Resolver entradas todas las remesas se dan en orden creciente en función del tiempo t<1000 de llegada, todos los instantes de llegada son diferentes, y todas las remesas contienen un único componente (o sea, m=1 siempre), como en el Ejemplo 1.

• Test2:  25 Puntos 

  Resolver entradas donde t, m, n<10⁴, como el Ejemplo 2.

• Test3:  35 Puntos 

  Resolver entradas donde t<10⁹, m, n<10⁴, como el Ejemplo 3.

• Test4:  10 Puntos 

  Resolver entradas donde t<10⁹ y m, n<10⁵.