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\ge 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:

  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:

  Resolver entradas donde $t, m, n<10^4$, como el Ejemplo 2.

• Test3:

  Resolver entradas donde $t<10^9$, $m, n<10^4$, como el Ejemplo 3.

• Test4:

  Resolver entradas donde $t<10^9$ y $m, n<10^5$.