Problema número 643

Kilos de basura

Tiempo máximo: 1,000-3,000 sMemoria máxima: 8192 KiB
Cubo de basura

Todas las noches igual. Cuando el cubo de basura se llena y toca salir a la calle para llevarla al contenedor terminamos discutiendo. Ninguno queremos ir.

El cubo tiene ya unos añitos, así que dentro de poco tendremos que cambiarlo. Y ya hace falta, que seguimos con un único cubo y por tanto no separamos por tipo de residuo. Nuestro objetivo es comprar un cubo de esos que admiten dos bolsas, una de envases y otra para el resto de basura, que nos garantice que el número de veces que tendremos que salir a la calle a vaciarlo no supere un umbral.

Para lograrlo llevamos tiempo analizando nuestros hábitos de consumo y de generación de residuos para escoger el cubo más apropiado. Durante estos últimos meses hemos ido apuntando todo lo que hemos ido tirando y tenemos una lista con lo que ocupa cada cosa y si iría a la bolsa de envases o a la otra.

El siguiente paso es decidir la capacidad que tiene que tener el cubo. Hemos visto que todos los que hay en el mercado con dos zonas tienen la zona de los envases con el doble de capacidad que la del resto de residuos (suponemos que será porque los envases en general ocupan más pero pesan menos). Para que no nos ocupe mucho en casa lo queremos lo más pequeño posible.

Entrada

La entrada está compuesta por distintos casos de prueba.

Cada caso de prueba comienza con una línea con dos números, K y N. El primero (entre 1 y 1.000) indica el número máximo de veces que estamos dispuestos a sacar la basura. El segundo (entre 1 y 200.000) indica la cantidad de datos recogidos.

A continuación aparecen N líneas con la información de las cosas que hemos ido tirando. Cada una comienza con un número indicando su tamaño (hasta 10.000) seguido de un carácter que puede ser E o R indicando que se tira un envase o un residuo genérico.

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

Salida

Por cada caso de prueba se escribirá la capacidad mínima de la bolsa de residuos genéricos que tiene que tener el cubo para que no necesitemos sacar la basura más de K veces para deshacernos de los N residuos. Hay que tener en cuenta que la capacidad se da siempre como un número entero y que salimos a tirar la basura cuando al ir al cubo a dejar algo, no entra; en ese momento salimos al contenedor, tiramos las dos bolsas y a la vuelta ponemos bolsas nuevas y "estrenamos" la que corresponda con aquello que no entró. El cubo comienza vacío y al final debe quedar vacío también.

Entrada de ejemplo

2 3
10 E
7 R
9 R
2 4
4 R
10 E
4 R
8 E
0 0

Salida de ejemplo

9
5